小直徑圖的導出匹配覆蓋

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

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

原晉江,Yuan Jinjiang(鄭州大學數學系,鄭州,450052) 

刊 名： 運籌學學報  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2008 12(2)  分類號： O22  關鍵詞： 運籌學   導出匹配   導出匹配覆蓋   NP-完備   多項式可解   Operations research   induced matching   induced matching cover   NP-complete   polynomially solvable  

【小直徑圖的導出匹配覆蓋】相關文章：

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

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

圖像匹配在海底地圖匹配中的應用04-26

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

區域覆蓋混合星座設計04-27

圖的倍圖與補倍圖04-26

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

一類最小覆蓋問題04-26

基站覆蓋規劃方案是否合理04-27

導出雙粒子糾纏態表象的新途徑04-26