The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(only showing first 100 items - show all)

Finding Hamiltonian circuits in quasi-adjoint graphs
Recent results on well-balanced orientations
2-Trees: Structural insights and the study of Hamiltonian paths
Complexity and stochastic evolution of dyadic networks
Acyclically 4-colorable triangulations
Jump number maximization for proper interval graphs and series-parallel graphs
Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
On the dominating (induced) cycles of iterated line graphs
Complete problems for space bounded subclasses of NP
On computing the Hamiltonian index of graphs
Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
scientific article; zbMATH DE number 2230201 (Why is no real title available?)
Computing the largest bond and the maximum connected cut of a graph
Induced tree covering and the generalized Yutsis property
Counting trees in a graph is \(\# \text{P}\)-complete
The longest path problem is polynomial on cocomparability graphs
Affine optimal k-proper connected edge colorings
1.6-approximation algorithm for generalized traveling salesman path problem
Packing 1-plane Hamiltonian cycles in complete geometric graphs
Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs
Distance-two colourings of Barnette graphs
Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
Hamiltonian path in permutation graphs
Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph
Two moves per time step make a difference
Domino sequencing: scheduling with state-based sequence-dependent setup times
On computing optimal linear diagrams
The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
Hamiltonian properties of locally connected graphs with bounded vertex degree
Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem
Satisfiability of co-nested formulas
Optimal covering of cacti by vertex-disjoint paths
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Hamiltonicity in Split Graphs - A Dichotomy
Deferred-query—An efficient approach for problems on interval and circular-arc graphs
Dynamics of cycles in polyhedra. I: The isolation lemma
The complexity of facets resolved
Embeddings of graphs
Counting substrate cycles in topologically restricted metabolic networks
Finding Hamiltonian circuits in proper interval graphs
Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
A linear time recognition algorithm for proper interval graphs
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
Restricted cycle factors and arc-decompositions of digraphs
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
The complexity of recognizing tough cubic graphs
Circuit and bond polytopes on series-parallel graphs
Complexity of the hamiltonian cycle in regular graph problem
Computing phylogenetic roots with bounded degrees and errors is NP-complete
Hamiltonian properties of polyhedra with few 3-cuts. A survey
Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
Circumscribing polygons and polygonizations for disjoint line segments
Parameterized complexity of Eulerian deletion problems
Path eccentricity of graphs
Graph theory (algorithmic, algebraic, and metric problems)
Shortest reconfiguration of perfect matchings via alternating cycles
Computing simple circuits from a set of line segments
Acyclic, star, and injective colouring: bounding the diameter
Aspects of upper defensive alliances
Hamiltonian problems in directed graphs with simple row patterns
On finding two-connected subgraphs in planar graphs
On the structure of Hamiltonian graphs with small independence number
Approximation hardness of graphic TSP on cubic graphs
Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits
Euclidean movement minimization
A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
Hamiltonian cycle curves in the space of discounted occupational measures
Complexity framework for forbidden subgraphs. I: The framework
Hardness of bounding influence via graph modification
NP-hard problems naturally arising in knot theory
Memory Efficient Anonymous Graph Exploration
Mine 'em all: a note on mining all graphs
Positive planar satisfiability problems under 3-connectivity constraints
The total interval number of a graph. III: Tree-like graphs.
Computing pivot-minors
Path partition for graphs with special blocks
Face covers and the genus problem for apex graphs
Hamiltonian index is NP-complete
Small \(k\)-pyramids and the complexity of determining \(k\)
Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
An explicit construction of graphs of bounded degree that are far from being Hamiltonian
A new integer programming formulation of the graphical traveling salesman problem
A new integer programming formulation of the graphical traveling salesman problem
Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
Pancyclicity and NP-completeness in planar graphs
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Games against nature
On the complexity of scheduling jobs on dedicated resources to minimize set-up costs
The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs
Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
Hardness and approximation results for black hole search in arbitrary networks
Some results on visibility graphs
A new upper bound for the traveling salesman problem in cubic graphs
Disconnected 2-factors in planar cubic bridgeless graphs
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

This page was built for publication: The Planar Hamiltonian Circuit Problem is NP-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4115165)