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

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

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

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

刊 名： 運(yùn)籌學(xué)學(xué)報(bào)  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2008 12(2)  分類(lèi)號(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-正則簡(jiǎn)單平面圖的完全刻畫(huà)04-26

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

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

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

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

升華法生長(zhǎng)大直徑的SiC單晶04-26

一類(lèi)最小覆蓋問(wèn)題04-26

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

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