NP-COMPLETENESS OF THE HAMILTONIAN CYCLE PROBLEM IN PLANAR DIGRAPHS WITH DEGREE BOUND 2

被引：70

作者：

PLESNIK, J

机构：

[1] Komensky University, Department of Mathematics

来源：

INFORMATION PROCESSING LETTERS | 1979年 / 8卷 / 04期

关键词：

Combinatorial problems; computational complexity;

D O I：

10.1016/0020-0190(79)90023-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

[No abstract available]

引用

页码：199 / 201

页数：3

共 7 条

[1]

Boesch, Gimpel, Covering the points of a digraph with point-disjoint paths and its application to code optimization, Journal of the ACM, 24, pp. 192-198, (1977)

[2]

Garey, Johnson, Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, pp. 237-267, (1976)

[3]

Garey, Johnson, Tarjan, The planar hamiltonian circuit problem is NP-complete, SIAM Journal on Computing, 5, pp. 704-714, (1976)

[4]

Harary, Graph theory, (1969)

[5]

Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp. 85-104, (1972)

[6]

Noltemeier, Reduktion von Pra¨zedenzstrukturen, Z. Operations Res., 20, pp. 151-159, (1976)

[7]

Sahni, Computationally related problems, SIAM Journal on Computing, 3, pp. 262-279, (1974)

← 1 →