The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
From MaRDI portal
Publication:1254855
DOI10.1016/0020-0190(79)90023-1zbMath0399.68070OpenAlexW1491169489WikidataQ56138402 ScholiaQ56138402MaRDI QIDQ1254855
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90023-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)
Related Items
Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, Largest \(j\)-simplices in \(n\)-polytopes, Hamiltonian problems in directed graphs with simple row patterns, Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Boundary classes for graph problems involving non-local properties, The complexity of approximate pattern matching on de Bruijn graphs, Sorting by Cuts, Joins and Whole Chromosome Duplications, On enumerating monomials and other combinatorial structures by polynomial interpolation, Reconfiguring (non-spanning) arborescences, Hardness of bounding influence via graph modification, The multi-stripe travelling salesman problem, Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs, The pumping lemma for regular languages is hard, Computational complexity of jumping block puzzles, On the complexity of the Eulerian closed walk with precedence path constraints problem, Unnamed Item, Parameterized complexity of Eulerian deletion problems, Arc-disjoint paths and trees in 2-regular digraphs, Unnamed Item, Topologically trivial closed walks in directed surface graphs, On the complexity of graph self-assembly in accretive systems, Gaming is a hard job, but someone has to do it!, Tractabilities and intractabilities on geometric intersection graphs, The complexity of routing with collision avoidance, The Asymmetric Travelling Salesman Problem In Sparse Digraphs., Unnamed Item, Moving coins, Counting substrate cycles in topologically restricted metabolic networks, Boundary properties of graphs for algorithmic graph problems, Unnamed Item, Traversability, reconfiguration, and reachability in the gadget framework, An algorithmic study of switch graphs, Complexity of token swapping and its variants, Simple Geometrical Intersection Graphs, Computational complexity of jumping block puzzles, Domino sequencing: scheduling with state-based sequence-dependent setup times, Flip distances between graph orientations, Unnamed Item, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Parameterized Complexity of Eulerian Deletion Problems, On a simple randomized algorithm for finding a 2-factor in sparse graphs, A cubic algorithm for the directed Eulerian subgraph problem, Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
Cites Work
- Unnamed Item
- Some simplified NP-complete graph problems
- Parallel concepts in graph theory
- Reduktion von Präzedenzstrukturen
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- Computationally Related Problems
