The Planar Hamiltonian Circuit Problem is NP-Complete
From MaRDI portal
Publication:4115165
DOI10.1137/0205049zbMath0346.05110MaRDI QIDQ4115165
Robert Endre Tarjan, David S. Johnson, Michael R. Garey
Publication date: 1976
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0205049
05C35: Extremal problems in graph theory
Related Items
Memory Efficient Anonymous Graph Exploration, Unnamed Item, Graph theory (algorithmic, algebraic, and metric problems), Computing simple circuits from a set of line segments, Hamiltonian circuits, Hamiltonian paths and branching graphs of benzenoid systems, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Computing phylogenetic roots with bounded degrees and errors is NP-complete, Graph factors and factorization: 1985--2003: a survey, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Connectivity of plane triangulations, Finding Hamiltonian circuits in quasi-adjoint graphs, Recent results on well-balanced orientations, Finding Hamiltonian circuits in proper interval graphs, Complete problems for space bounded subclasses of NP, Finding Hamiltonian circuits in interval graphs, Games against nature, Hamiltonian circuits in interval graph generalizations, On mapping processes to processors in distributed systems, The complexity of facets resolved, A note on the traveling salesman problem, On the complexity of scheduling jobs on dedicated resources to minimize set-up costs, Context-free grammars as a tool for describing polynomial-time subclasses of hard problems, The edge Hamiltonian path problem is NP-complete, Optimal covering of cacti by vertex-disjoint paths, NP-completeness and degree restricted spanning trees, Some results on visibility graphs, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, Embeddings of graphs, Satisfiability of co-nested formulas, Complexity of the hamiltonian cycle in regular graph problem, Counting trees in a graph is \(\# \text{P}\)-complete, On problems with short certificates, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, The complexity of recognizing tough cubic graphs, On finding two-connected subgraphs in planar graphs, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., The complexity of the locally connected spanning tree problem, Path partition for graphs with special blocks, Jump number maximization for proper interval graphs and series-parallel graphs, An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs, Face covers and the genus problem for apex graphs, Disconnected 2-factors in planar cubic bridgeless graphs, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs, Pancyclicity and NP-completeness in planar graphs, Hardness and approximation results for black hole search in arbitrary networks, Each maximal planar graph with exactly two separating triangles is Hamiltonian, Good triangulations yield good tours, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Complexity and stochastic evolution of dyadic networks, Matching and spanning in certain planar graphs, Unnamed Item, The adjacency relation on the traveling salesman polytope is NP-Complete, NP-Complete operations research problems and approximation algorithms
