The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(only showing first 100 items - show all)

A linear time recognition algorithm for proper interval graphs
Labeling schemes for tree representation
On a simple randomized algorithm for finding a 2-factor in sparse graphs
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
The parity Hamiltonian cycle problem
The complexity of routing with collision avoidance
Tree-based unrooted phylogenetic networks
Circuit and bond polytopes on series-parallel graphs
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
The longest path problem is polynomial on cocomparability graphs
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Pancyclicity and NP-completeness in planar graphs
Counting substrate cycles in topologically restricted metabolic networks
Aspects of upper defensive alliances
Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs
Hamiltonian cycle curves in the space of discounted occupational measures
On the dominating (induced) cycles of iterated line graphs
Two Hamiltonian cycles
Königsberg sightseeing: Eulerian walks in temporal graphs
Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
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
Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
Existence and hardness of conveyor belts
Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs
Distance-two colourings of Barnette graphs
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
A new upper bound for the traveling salesman problem in cubic graphs
Small \(k\)-pyramids and the complexity of determining \(k\)
A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
Wooden geometric puzzles: Design and hardness proofs
Nontrivial path covers of graphs: existence, minimization and maximization
Domino sequencing: scheduling with state-based sequence-dependent setup times
On the computational complexity of length- and neighborhood-constrained path problems
Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
Edge-outer graph embedding and the complexity of the DNA reporter strand problem
Reliability problems in multiple path-shaped facility location on networks
Restricted cycle factors and arc-decompositions of digraphs
All-shortest-path 2-interval routing is NP-complete
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
On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph
A linear-time algorithm for finding Hamiltonian (s,t)-paths in even-sized rectangular grid graphs with a rectangular hole
Construction sequences and certifying 3-connectivity
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
Exact algorithms for the Hamiltonian cycle problem in planar graphs
2-edge-Hamiltonian-connectedness of 4-connected plane graphs
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Complexity and stochastic evolution of dyadic networks
Decycling with a matching
Acyclically 4-colorable triangulations
Computing the largest bond and the maximum connected cut of a graph
Circumscribing polygons and polygonizations for disjoint line segments
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
On computing the Hamiltonian index of graphs
Mine 'em all: a note on mining all graphs
Hamiltonicity in Split Graphs - A Dichotomy
TSP on cubic and subcubic graphs
Matching and spanning in certain planar graphs
The longest path problem is polynomial on cocomparability graphs
Euclidean movement minimization
Parameterized complexity of Eulerian deletion problems
Planar k-path in subexponential time and polynomial space

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)