运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2012年
3期
139-144
,共6页
k-步长控制%k-距离控制%NP-完全性%弦图%平面二部图
k-步長控製%k-距離控製%NP-完全性%絃圖%平麵二部圖
k-보장공제%k-거리공제%NP-완전성%현도%평면이부도
k-step domination%k-distance domination%NP-completeness%chordal graphs%planar bipartite graphs
研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题,证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的.作为上述结果的推论,给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明,并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.
研究兩類廣義控製問題的複雜性: k-步長控製問題和k-距離控製問題,證明瞭k-步長控製問題在絃圖和平麵二部圖上都是NP-完全的.作為上述結果的推論,給齣瞭k-距離控製問題在絃圖和二部圖上NP-完全性的新的證明,併進一步證明瞭k-距離控製問題在平麵二部圖上也是NP-完全的.
연구량류엄의공제문제적복잡성: k-보장공제문제화k-거리공제문제,증명료k-보장공제문제재현도화평면이부도상도시NP-완전적.작위상술결과적추론,급출료k-거리공제문제재현도화이부도상NP-완전성적신적증명,병진일보증명료k-거리공제문제재평면이부도상야시NP-완전적.
We study the complexity of two classes of generalized domination problems:k-step domination problem and k-distance domination problem. We prove that the decision version of k-step domination problem is NP-complete when instances are restricted to chordal graphs or planar bipartite graphs.As corollaries to the results,we obtain new proofs of the NP-completeness of k-distance domination problem for chordal graphs and bipartite graphs,and also prove that this problem remains NP-complete even when restricted to planar bipartite graphs.
