NP-COMPLETENESS OF MINIMUM SPANNER PROBLEMS

被引:43
作者
CAI, LH
机构
[1] Department of Computer Science, University of Toronto, Toronto
关键词
D O I
10.1016/0166-218X(94)90073-6
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. This notion is motivated by applications in distributed systems, communication networks, computational geometry and robotics. In this paper, it is shown that for any fixed t greater-than-or-equal-to 2, the problem of determining, for a graph G and a positive integer K, whether G contains a t-spanner with at most K edges is NP-complete, even if G is a bipartite graph (for fixed t greater-than-or-equal-to 3). The problem for digraphs is also shown to be NP-complete, even for oriented graphs (with fixed t greater-than-or-equal-to 3).
引用
收藏
页码:187 / 194
页数:8
相关论文
共 50 条
[41]   Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics [J].
Cheng, XZ ;
Narahari, B ;
Simha, R ;
Cheng, MXY ;
Liu, D .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2003, 2 (03) :248-256
[42]   Selfish splittable flows and NP-completeness [J].
Kaporis, A. C. ;
Spirakis, P. G. .
COMPUTER SCIENCE REVIEW, 2011, 5 (03) :209-228
[43]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS, 1984, 5 (03) :433-447
[44]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS, 1988, 9 (03) :426-444
[45]   Pancyclicity and NP-completeness in planar graphs [J].
Li, MC ;
Corneil, DG ;
Mendelsohn, E .
DISCRETE APPLIED MATHEMATICS, 2000, 98 (03) :219-225
[46]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1986, 7 (02) :289-305
[47]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS, 1982, 3 (03) :288-300
[48]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (01) :145-159
[49]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS, 1987, 8 (02) :285-303
[50]   THE NP-COMPLETENESS OF EDGE-COLORING [J].
HOLYER, I .
SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720