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 条
  • [21] MULTIPROCESSOR SOLUTION IN OCCAM TO AN NP-COMPLETE PROBLEM
    HEAL, B
    MICROPROCESSORS AND MICROSYSTEMS, 1985, 9 (04) : 162 - 170
  • [22] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE
    GAREY, MR
    JOHNSON, DS
    SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) : 826 - 834
  • [23] Timed protocol insecurity problem is NP-complete
    Benerecetti, Massimo
    Peron, Adriano
    FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2013, 29 (03): : 843 - 862
  • [24] Broadcasting with the least energy is an NP-complete problem
    Yang, Wuu
    Tseng, Huei-Ru
    Jan, Rong-Hong
    Shen, Bor-Yeh
    MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS, 2008, : 197 - 200
  • [25] The rectilinear Steiner arborescence problem is NP-complete
    Shi, WP
    Su, C
    SIAM JOURNAL ON COMPUTING, 2006, 35 (03) : 729 - 740
  • [26] An NP-complete Problem for the Abelian Sandpile Model
    Schulz, Matthias
    COMPLEX SYSTEMS, 2007, 17 (01): : 17 - 28
  • [27] The Rectilinear Steiner Arborescence problem is NP-complete
    Shi, WP
    Su, C
    PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2000, : 780 - 787
  • [28] FINDING HAMILTONIAN CIRCUITS IN ARRANGEMENTS OF JORDAN CURVES IS NP-COMPLETE
    IWAMOTO, C
    TOUSSAINT, GT
    INFORMATION PROCESSING LETTERS, 1994, 52 (04) : 183 - 189
  • [29] THE SHORTEST COMMON NONSUBSEQUENCE PROBLEM IS NP-COMPLETE
    MIDDENDORF, M
    THEORETICAL COMPUTER SCIENCE, 1993, 108 (02) : 365 - 369
  • [30] NP-COMPLETE NUMBER-THEORETIC PROBLEM
    GURARI, EM
    IBARRA, OH
    JOURNAL OF THE ACM, 1979, 26 (03) : 567 - 581
12345