The Planar Hamiltonian Circuit Problem is NP-Complete
From MaRDI portal
Publication:4115165
DOI10.1137/0205049zbMath0346.05110OpenAlexW2087818742MaRDI QIDQ4115165
Michael R. Garey, David S. Johnson, Robert Endre Tarjan
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
Related Items
On Finding Hamiltonian Cycles in Barnette Graphs, On Computing the Hamiltonian Index of Graphs, Decycling with a matching, All-shortest-path 2-interval routing is NP-complete, Deferred-query—An efficient approach for problems on interval and circular-arc graphs, Memory Efficient Anonymous Graph Exploration, Hardness and approximation results for black hole search in arbitrary networks, The Longest Path Problem Is Polynomial on Interval Graphs, Each maximal planar graph with exactly two separating triangles is Hamiltonian, Good triangulations yield good tours, Unnamed Item, Unnamed Item, On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph, Approximation hardness of graphic TSP on cubic graphs, Editing to a Planar Graph of Given Degrees, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Nominal Unification and Matching of Higher Order Expressions with Recursive Let, A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole, Packing 1-plane Hamiltonian cycles in complete geometric graphs, A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs, On temporal graph exploration, Computing the largest bond and the maximum connected cut of a graph, Circumscribing polygons and polygonizations for disjoint line segments, Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture, Optimizing concurrency under Scheduling by Edge Reversal, On computing optimal linear diagrams, Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy, 2-Trees: Structural insights and the study of Hamiltonian paths, Path eccentricity of graphs, Hardness of bounding influence via graph modification, Construction sequences and certifying 3-connectivity, Eulerian walks in temporal graphs, Can local optimality be used for efficient data reduction?, Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes, Hamiltonian Cycles and Subsets of Discounted Occupational Measures, Hamiltonicity in Split Graphs - A Dichotomy, On computing the Hamiltonian index of graphs, The st-bond polytope on series-parallel graphs, Parameterized complexity of Eulerian deletion problems, The traveling salesman problem on cubic and subcubic graphs, Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices, On the computational complexity of centers locating in a graph, TSP on Cubic and Subcubic Graphs, On the Minimum Number of Hamiltonian Cycles in Regular Graphs, Contracting to a longest path in H-free graphs, Some natural decision problems in automatic graphs, Unnamed Item, Unnamed Item, Matching and spanning in certain planar graphs, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Traversability, reconfiguration, and reachability in the gadget framework, Unnamed Item, The adjacency relation on the traveling salesman polytope is NP-Complete, Unnamed Item, The Longest Path Problem is Polynomial on Cocomparability Graphs, 2-edge-Hamiltonian-connectedness of 4-connected plane graphs, Aligned Drawings of Planar Graphs, The Parameterized Complexity of Graph Cyclability, A new integer programming formulation of the graphical traveling salesman problem, Drawing graphs as spanners, Acyclic, star, and injective colouring: bounding the diameter, A new integer programming formulation of the graphical traveling salesman problem, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, NP-Complete operations research problems and approximation algorithms, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Approximation Algorithms for Facial Cycles in Planar Embeddings, Mine ’Em All: A Note on Mining All Graphs, Unnamed Item, Parameterized Complexity of Eulerian Deletion Problems, Planar k-Path in Subexponential Time and Polynomial Space, More Efficient Periodic Traversal in Anonymous Undirected Graphs, NP–hard problems naturally arising in knot theory, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Complexity and stochastic evolution of dyadic networks, Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs, Feasible Bases for a Polytope Related to the Hamilton Cycle Problem, Restricted cycle factors and arc-decompositions of digraphs, Acyclically 4-colorable triangulations, Visibility representations of boxes in 2.5 dimensions, Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph, Complexity of the hamiltonian cycle in regular graph problem, Counting trees in a graph is \(\# \text{P}\)-complete, Cyclability in graph classes, On problems with short certificates, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, Hamiltonian circuits in interval graph generalizations, Euclidean movement minimization, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, On mapping processes to processors in distributed systems, Hamiltonian problems in directed graphs with simple row patterns, Positive planar satisfiability problems under 3-connectivity constraints, StreamTable: an area proportional visualization for tables with flowing streams, Nested locally Hamiltonian graphs and the Oberly-Sumner conjecture, The parameterised complexity of list problems on graphs of bounded treewidth, The complexity of facets resolved, Computing phylogenetic roots with bounded degrees and errors is NP-complete, Graph factors and factorization: 1985--2003: a survey, A note on the traveling salesman problem, The complexity of recognizing tough cubic graphs, On finding two-connected subgraphs in planar graphs, Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs, The parameterized complexity of local search for TSP, more refined, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), UNO is hard, even for a single player, The parity Hamiltonian cycle problem, Interdiction problems on planar graphs, The longest path problem is polynomial on cocomparability graphs, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs, Hamiltonian index is NP-complete, The complexity of the locally connected spanning tree problem, On the complexity of scheduling jobs on dedicated resources to minimize set-up costs, Split Euler tours in 4-regular planar graphs, The longest path problem has a polynomial solution on interval graphs, Connectivity of plane triangulations, More efficient periodic traversal in anonymous undirected graphs, Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits, Existence and hardness of conveyor belts, Hamiltonian properties of locally connected graphs with bounded vertex degree, The 1-fixed-endpoint path cover problem is Polynomial on interval graphs, Context-free grammars as a tool for describing polynomial-time subclasses of hard problems, Pancyclicity and NP-completeness in planar graphs, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, The edge Hamiltonian path problem is NP-complete, Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs, Distance-two colourings of Barnette graphs, Optimal covering of cacti by vertex-disjoint paths, Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, The complexity of routing with collision avoidance, Spanning trees with nonseparating paths, Tree-based unrooted phylogenetic networks, Hamiltonian circuits, Hamiltonian paths and branching graphs of benzenoid systems, Circuit and bond polytopes on series-parallel graphs, Finding Hamiltonian circuits in quasi-adjoint graphs, Recent results on well-balanced orientations, NP-completeness and degree restricted spanning trees, A new upper bound for the traveling salesman problem in cubic graphs, Some results on visibility graphs, Small \(k\)-pyramids and the complexity of determining \(k\), Path partition for graphs with special blocks, Counting substrate cycles in topologically restricted metabolic networks, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, Wooden geometric puzzles: Design and hardness proofs, Graph theory (algorithmic, algebraic, and metric problems), Aspects of upper defensive alliances, Computing simple circuits from a set of line segments, Hamiltonian properties of polyhedra with few 3-cuts. A survey, Editing to a planar graph of given degrees, Nontrivial path covers of graphs: existence, minimization and maximization, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, Domino sequencing: scheduling with state-based sequence-dependent setup times, On the computational complexity of length- and neighborhood-constrained path problems, A linear time recognition algorithm for proper interval graphs, Labeling schemes for tree representation, Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Zen puzzle garden is NP-complete, Edge-outer graph embedding and the complexity of the DNA reporter strand problem, On a simple randomized algorithm for finding a 2-factor in sparse graphs, An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Finding Hamiltonian circuits in proper interval graphs, Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs, Hamiltonian cycle curves in the space of discounted occupational measures, Face covers and the genus problem for apex graphs, Disconnected 2-factors in planar cubic bridgeless graphs, Reliability problems in multiple path-shaped facility location on networks, On the dominating (induced) cycles of iterated line graphs, Embeddings of graphs, Complete problems for space bounded subclasses of NP, Finding Hamiltonian circuits in interval graphs, Games against nature, Two Hamiltonian cycles, Königsberg sightseeing: Eulerian walks in temporal graphs, Satisfiability of co-nested formulas
