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 条
[31]   Nonuniform Reductions and NP-Completeness [J].
Hitchcock, John M. ;
Shafei, Hadi .
THEORY OF COMPUTING SYSTEMS, 2022, 66 (04) :743-757
[32]   ON NP-COMPLETENESS IN LINEAR LOGIC [J].
KOPYLOV, AP .
ANNALS OF PURE AND APPLIED LOGIC, 1995, 75 (1-2) :137-152
[33]   NP-COMPLETENESS AND DEGREES OF SATISFACTION [J].
LIEBERHERR, K .
JOURNAL OF SYMBOLIC LOGIC, 1977, 42 (03) :457-457
[34]   NP-completeness of the game Kingdomino™ [J].
Viet-Ha Nguyen ;
Perrot, Kevin ;
Vallet, Mathieu .
THEORETICAL COMPUTER SCIENCE, 2020, 822 :23-35
[35]   NP-completeness in hedonic games [J].
Ballester, C .
GAMES AND ECONOMIC BEHAVIOR, 2004, 49 (01) :1-30
[36]   Query order and NP-completeness [J].
Dai, JJ ;
Lutz, JH .
FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, :142-148
[37]   NP-Completeness in the gossip monoid [J].
Fenner, Peter ;
Johnson, Marianne ;
Kambites, Mark .
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2018, 28 (04) :653-672
[38]   Nonuniform Reductions and NP-Completeness [J].
Hitchcock, John M. ;
Shafei, Hadi .
35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96
[39]   AN ELEMENTARY APPROACH TO NP-COMPLETENESS [J].
AUSTIN, AK .
AMERICAN MATHEMATICAL MONTHLY, 1983, 90 (06) :398-399
[40]   NP-COMPLETENESS OF SOME EDGE-DISJOINT PATHS PROBLEMS [J].
VYGEN, J .
DISCRETE APPLIED MATHEMATICS, 1995, 61 (01) :83-90