NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs

スポンサーリンク

概要

• 論文の詳細を見る

• We consider the problem of determining whether a bipartite graph G has a hamiltonian cycle. We show that this problem is NP-complete for two classes of bipartite graphs: 2-connected cubic bipartite planar graphs; and 3-connected cubic bipartite graphs. Hence the hamiltonian cycle problem for these classes of graphs, or any larger class containing all such graphs, is probably computationally intractable.

• 一般社団法人情報処理学会の論文
• 1980-08-31

著者

• Nishizeki Takao

  Department Of Electrical Communications Faculty Of Engineering Tohoku University

• SAITO NOBUJI

  Department of Electrical Communications, Faculty of Engineering, Tohoku University

• Saito Nobuji

  Department Of Electrical Communications Faculty Of Engineering Tohoku University

• AKIYAMA TAKANORI

  Department of Electrical Communications, Faculty of Engineering, Tohoku University

• Akiyama Takanori

  Department Of Electrical Communications Faculty Of Engineering Tohoku University

• NISHIZEKI TAKAO

  Department of Electrical Communications, Faculty of Engineering, Tohoku University

関連論文

• Applications of the Lipton and Tarjan's Planar Separator Theorem
• Applications of the Lipton and Tarjan's Planar Separator Theorem (Applied Combinatorial Theory and Algorithms)
• Optimal Parallel Algorithms for Edge-Coloring Partial k-Trees with Bounded Degrees
• Editors' Introduction to Special Section on Discrete Algorithms and Complexity
• NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs
• Structure and Function of NO reductase with oxygen-reducing activity

スポンサーリンク