scientific article

Nobuji Saito, Takanori Akiyama, Takao Nishizeki

Publication date: 1980

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

NP-completeness bipartite graphs Hamiltonian cycle problem

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

On Finding Hamiltonian Cycles in Barnette Graphs, Global cycle properties of locally isometric graphs, Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs, Visibility representations of boxes in 2.5 dimensions, A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs, Cyclability in graph classes, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, Bipartite permutation graphs, On Hamiltonicity of regular graphs with bounded second neighborhoods, Hamiltonian problems in directed graphs with simple row patterns, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, Unnamed Item, The complexity of recognizing tough cubic graphs, On line graphs of subcubic triangle-free graphs, Boundary classes for graph problems involving non-local properties, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, Construction of Barnette graphs whose large subgraphs are non-Hamiltonian, Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture, Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy, Hamiltonicity of locally Hamiltonian and locally traceable graphs, 2-Trees: Structural insights and the study of Hamiltonian paths, Hamiltonicity in Split Graphs - A Dichotomy, Gray codes with bounded weights, Hamiltonian properties of locally connected graphs with bounded vertex degree, Unnamed Item, Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane, The traveling salesman problem on cubic and subcubic graphs, A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, Independent feedback vertex set for \(P_5\)-free graphs, TSP on Cubic and Subcubic Graphs, Finding Hamiltonian circuits in quasi-adjoint graphs, Finding induced trees, On Barnette's conjecture, Counting substrate cycles in topologically restricted metabolic networks, The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Remarks on Barnette's conjecture, Non-preemptive tree packing, Global Curve Simplification, Walking through waypoints, Non-preemptive tree packing, A note on the Hamiltonian circuit problem on directed path graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., \( 1 / 2\)-conjectures on the domination game and claw-free graphs, Global cycle properties in graphs with large minimum clustering coefficient, A note on the smallest connected non-traceable cubic bipartite planar graph, Revising Johnson's table for the 21st century, Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem