A note on the Hamiltonian circuit problem on directed path graphs

DOI10.1016/0020-0190(89)90038-0zbMath0685.68052OpenAlexW2127206007MaRDI QIDQ1262132

Giri Narasimhan

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/59108

zbMATH Keywords

Hamiltonian circuitcliquesNP-completedirected path graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

The longest path problem is polynomial on cocomparability graphs ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Intersection graphs of non-crossing paths ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Intersection graphs of paths in a tree
• Hamiltonian circuits in interval graph generalizations
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness column: an ongoing guide
• Total domination in graphs
• Hamilton Paths in Grid Graphs

This page was built for publication: A note on the Hamiltonian circuit problem on directed path graphs