The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(only showing first 100 items - show all)

The Longest Path Problem Is Polynomial on Interval Graphs
Two Hamiltonian cycles
Complete problems for space bounded subclasses of NP
Tree-based unrooted phylogenetic networks
Complexity of the hamiltonian cycle in regular graph problem
An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
Graph factors and factorization: 1985--2003: a survey
The parameterised complexity of list problems on graphs of bounded treewidth
Graph theory (algorithmic, algebraic, and metric problems)
NP-hard problems naturally arising in knot theory
Computing simple circuits from a set of line segments
Counting trees in a graph is \(\# \text{P}\)-complete
Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
Pancyclicity and NP-completeness in planar graphs
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Finding Hamiltonian circuits in proper interval graphs
The complexity of the locally connected spanning tree problem
Hardness and approximation results for black hole search in arbitrary networks
Deferred-query—An efficient approach for problems on interval and circular-arc graphs
TSP on cubic and subcubic graphs
Editing to a planar graph of given degrees
The traveling salesman problem on cubic and subcubic graphs
The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
The adjacency relation on the traveling salesman polytope is NP-Complete
On Computing the Hamiltonian Index of Graphs
On the minimum number of Hamiltonian cycles in regular graphs
Good triangulations yield good tours
Algorithms for solving problems on graphs of bounded pathwidth
On the computational complexity of length- and neighborhood-constrained path problems
Editing to a planar graph of given degrees
Face covers and the genus problem for apex graphs
On mapping processes to processors in distributed systems
Hamiltonian circuits, Hamiltonian paths and branching graphs of benzenoid systems
An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits
A linear time recognition algorithm for proper interval graphs
A new upper bound for the traveling salesman problem in cubic graphs
The parameterized complexity of local search for TSP, more refined
Games against nature
The complexity of facets resolved
Aligned drawings of planar graphs
The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
Jump number maximization for proper interval graphs and series-parallel graphs
2-edge-Hamiltonian-connectedness of 4-connected plane graphs
Optimal covering of cacti by vertex-disjoint paths
Approximation hardness of graphic TSP on cubic graphs
Some results on visibility graphs
Parameterized complexity of Eulerian deletion problems
The longest path problem is polynomial on cocomparability graphs
A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
Euclidean movement minimization
Each maximal planar graph with exactly two separating triangles is Hamiltonian
Cyclability in graph classes
Hamiltonian properties of polyhedra with few 3-cuts. A survey
On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph
Not being (super)thin or solid is hard: A study of grid Hamiltonicity
Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
Hamiltonian properties of locally connected graphs with bounded vertex degree
Hamiltonian index is NP-complete
Complexity and stochastic evolution of dyadic networks
Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
NP-completeness and degree restricted spanning trees
Parameterized complexity of Eulerian deletion problems
Disconnected 2-factors in planar cubic bridgeless graphs
A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
Spanning trees with nonseparating 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
Finding Hamiltonian circuits in interval graphs
On computing the Hamiltonian index of graphs
UNO is hard, even for a single player
The edge Hamiltonian path problem is NP-complete
Acyclically 4-colorable triangulations
scientific article; zbMATH DE number 2230201 (Why is no real title available?)
More efficient periodic traversal in anonymous undirected graphs
Exact algorithms for the Hamiltonian cycle problem in planar graphs
The longest path problem has a polynomial solution on interval graphs
On the computational complexity of centers locating in a graph
Satisfiability of co-nested formulas
Hamiltonian circuits in interval graph generalizations
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Connectivity of plane triangulations
The complexity of recognizing tough cubic graphs
Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs
On a simple randomized algorithm for finding a 2-factor in sparse graphs
Path eccentricity of graphs
Packing 1-plane Hamiltonian cycles in complete geometric graphs
The complexity of routing with collision avoidance
All-shortest-path 2-interval routing is NP-complete
Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
More efficient periodic traversal in anonymous undirected graphs
On Finding Hamiltonian Cycles in Barnette Graphs
Finding Hamiltonian circuits in quasi-adjoint graphs
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
Recent results on well-balanced orientations
Positive planar satisfiability problems under 3-connectivity constraints
Nested locally Hamiltonian graphs and the Oberly-Sumner conjecture
Matching and spanning in certain planar graphs
Aspects of upper defensive alliances

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)