- 相關(guān)推薦
小直徑圖的導(dǎo)出匹配覆蓋
設(shè)G是一個圖,而M1,M2,…,Mk是G的k個導(dǎo)出匹配.稱{M1,M2,…,Mk}是圖G的一個k-導(dǎo)出匹配覆蓋,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-導(dǎo)出匹配覆蓋問題是指對任一個給定的圖G是否存在一個k-導(dǎo)出匹配覆蓋.這篇文章證明了:直徑為6的圖的2-導(dǎo)出匹配覆蓋問題和直徑為2的圖的3-導(dǎo)出匹配覆蓋問題是NP-完備的,直徑為2的圖的2-導(dǎo)出匹配覆蓋問題多項式可解.
作 者： 董麗 原晉江 Dong Li Yuan Jinjiang 作者單位： 董麗,Dong Li(信陽師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,信陽,464000)原晉江,Yuan Jinjiang(鄭州大學(xué)數(shù)學(xué)系,鄭州,450052)
刊 名： 運籌學(xué)學(xué)報 ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS 年，卷(期)： 2008 12(2) 分類號： O22 關(guān)鍵詞： 運籌學(xué) 導(dǎo)出匹配 導(dǎo)出匹配覆蓋 NP-完備 多項式可解 Operations research induced matching induced matching cover NP-complete polynomially solvable【小直徑圖的導(dǎo)出匹配覆蓋】相關(guān)文章：
具最小度距離的完美匹配單圈圖04-26
直徑為3的3-正則簡單平面圖的完全刻畫04-26
大直徑FZSi中的微缺陷研究04-27
區(qū)域覆蓋混合星座設(shè)計04-27
圖的倍圖與補倍圖04-26
升華法生長大直徑的SiC單晶04-26
一類最小覆蓋問題04-26
基站覆蓋規(guī)劃方案是否合理04-27