小直徑圖的導(dǎo)出匹配覆蓋

設(shè)G是一個(gè)圖,而M1,M2,…,Mk是G的k個(gè)導(dǎo)出匹配.稱{M1,M2,…,Mk}是圖G的一個(gè)k-導(dǎo)出匹配覆蓋,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-導(dǎo)出匹配覆蓋問題是指對(duì)任一個(gè)給定的圖G是否存在一個(gè)k-導(dǎo)出匹配覆蓋.這篇文章證明了:直徑為6的圖的2-導(dǎo)出匹配覆蓋問題和直徑為2的圖的3-導(dǎo)出匹配覆蓋問題是NP-完備的,直徑為2的圖的2-導(dǎo)出匹配覆蓋問題多項(xiàng)式可解.

作 者： 董麗 原晉江 Dong Li Yuan Jinjiang   作者單位： 董麗,Dong Li(信陽師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,信陽,464000)

原晉江,Yuan Jinjiang(鄭州大學(xué)數(shù)學(xué)系,鄭州,450052) 

刊 名： 運(yùn)籌學(xué)學(xué)報(bào)  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2008 12(2)  分類號(hào)： O22  關(guān)鍵詞： 運(yùn)籌學(xué)   導(dǎo)出匹配   導(dǎo)出匹配覆蓋   NP-完備   多項(xiàng)式可解   Operations research   induced matching   induced matching cover   NP-complete   polynomially solvable  

【小直徑圖的導(dǎo)出匹配覆蓋】相關(guān)文章：

具最小度距離的完美匹配單圈圖04-26

直徑為3的3-正則簡單平面圖的完全刻畫04-26

圖像匹配在海底地圖匹配中的應(yīng)用04-26

大直徑FZSi中的微缺陷研究04-27

區(qū)域覆蓋混合星座設(shè)計(jì)04-27

圖的倍圖與補(bǔ)倍圖04-26

升華法生長大直徑的SiC單晶04-26

一類最小覆蓋問題04-26

基站覆蓋規(guī)劃方案是否合理04-27

導(dǎo)出雙粒子糾纏態(tài)表象的新途徑04-26