THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE

被引：71
|
作者：
BERTOSSI, AA
机构：
来源：
INFORMATION PROCESSING LETTERS | 1981年 / 13卷 / 4-5期
关键词：
D O I：
10.1016/0020-0190(81)90048-X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：157 / 159
页数：3
相关论文
共 50 条
  • [31] The 2-Attractor Problem Is NP-Complete
    Fuchs, Janosch
    Whittington, Philip
    41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024, 2024, 289
  • [32] MIN CUT IS NP-COMPLETE FOR EDGE WEIGHTED TREES
    MONIEN, B
    SUDBOROUGH, IH
    LECTURE NOTES IN COMPUTER SCIENCE, 1986, 226 : 265 - 274
  • [33] MIN CUT IS NP-COMPLETE FOR EDGE WEIGHTED TREES
    MONIEN, B
    SUDBOROUGH, IH
    THEORETICAL COMPUTER SCIENCE, 1988, 58 (1-3) : 209 - 229
  • [34] The edge-disjoint paths problem is NP-complete for series-parallel graphs
    Nishizeki, T
    Vygen, J
    Zhou, X
    DISCRETE APPLIED MATHEMATICS, 2001, 115 (1-3) : 177 - 186
  • [35] The edge-disjoint paths problem is NP-complete for partial k-trees
    Zhou, X
    Nishizeki, T
    ALGORITHMS AND COMPUTATIONS, 1998, 1533 : 417 - 426
  • [36] Solving NP-Complete Problem Using ACO Algorithm
    Asif, Muhammad
    Baig, Rauf
    ICET: 2009 INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES, PROCEEDINGS, 2009, : 13 - 16
  • [37] Hashiwokakero is NP-complete
    Andersson, Daniel
    INFORMATION PROCESSING LETTERS, 2009, 109 (19) : 1145 - 1146
  • [38] Minesweeper is NP-complete
    Richard Kaye
    The Mathematical Intelligencer, 2000, 22 : 9 - 15
  • [39] Shellability is NP-complete
    Goaoc, Xavier
    Patak, Pavel
    Patakova, Zuzana
    Tancer, Martin
    Wagner, Uli
    JOURNAL OF THE ACM, 2019, 66 (03)
  • [40] A NATURAL NP-COMPLETE PROBLEM WITH A NONTRIVIAL LOWER BOUND
    GRANDJEAN, E
    JOURNAL OF SYMBOLIC LOGIC, 1987, 52 (01) : 321 - 321
12345