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 (only showing first 100 items - show all)
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 ⋮ Parameterizing path partitions ⋮ 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 ⋮ Induced tree covering and the generalized Yutsis property ⋮ Connected proper interval graphs and the guard problem in spiral polygons (extended abstract) ⋮ 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 ⋮ Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy ⋮ A new integer programming formulation of the graphical traveling salesman problem ⋮ StreamTable: an area proportional visualization for tables with flowing streams ⋮ 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
This page was built for publication: The Planar Hamiltonian Circuit Problem is NP-Complete
