On the complexity of hamiltonian path and cycle problems in certain classes of digraphs

DOI10.1016/S0166-218X(99)00064-5zbMath0934.05082OpenAlexW1984883238WikidataQ128066106 ScholiaQ128066106MaRDI QIDQ1302144

Gregory Gutin, Jörgen Bang-Jensen

Publication date: 9 April 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00064-5

zbMATH Keywords

parallel algorithmpolynomial algorithmHamilton pathHamilton cyclequasi-transitive digraphsemicomplete multipartite digraphpath-mergeable digraphtournament locally in-semicomplete digraph

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

Classification of de Bruijn-based labeled digraphs ⋮ Semicomplete Multipartite Digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions

This page was built for publication: On the complexity of hamiltonian path and cycle problems in certain classes of digraphs