NP-COMPLETENESS OF MINIMUM SPANNER PROBLEMS

被引:44
作者
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 条
[21]   NP-COMPLETENESS OF THE PROBLEMS OF CONSTRUCTION OF OPTIMAL SOLVING TREES [J].
NAUMOV, GY .
DOKLADY AKADEMII NAUK SSSR, 1991, 317 (04) :850-853
[22]   NP-COMPLETENESS OF SOME PROBLEMS CONCERNING VOTING GAMES [J].
PRASAD, K ;
KELLY, JS .
INTERNATIONAL JOURNAL OF GAME THEORY, 1990, 19 (01) :1-9
[23]   NP-completeness of some tree-clustering problems [J].
Schreiber, F ;
Skodinis, K .
GRAPH DRAWING, 1998, 1547 :288-301
[24]   Separation of NP-completeness notions [J].
Pavan, A ;
Selman, AL .
SIAM JOURNAL ON COMPUTING, 2002, 31 (03) :906-918
[25]   Brick wall: NP-completeness [J].
Franco, John .
IEEE Potentials, 1997, 16 (04) :37-40
[26]   Separation of NP-completeness notions [J].
Pavan, A ;
Selman, AL .
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, :78-89
[27]   SUBPROBLEMS AND NP-COMPLETENESS THEORY [J].
Su, Li Sek .
BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE, 2006, (90) :192-198
[28]   On NP-completeness for linear machines [J].
Gassner, C .
JOURNAL OF COMPLEXITY, 1997, 13 (02) :259-271
[29]   NP-completeness of kSAT and multifractals [J].
Sato, Y ;
Taiji, M ;
Ikegami, T .
COMPUTER PHYSICS COMMUNICATIONS, 1999, 121 :51-53
[30]   Nonuniform Reductions and NP-Completeness [J].
John M. Hitchcock ;
Hadi Shafei .
Theory of Computing Systems, 2022, 66 :743-757