A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs

DOI10.1016/0196-6774(92)90008-ZMaRDI QIDQ3990618zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen, Jørgen Bang-Jensen, Y. Manoussakis

Publication date 28 June 1992

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(92)90008-z

zbMATH Keywords

Hamiltonian pathpolynomial algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• A successful algorithm for solving directed Hamiltonian path problems
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• scientific article; zbMATH DE number 1439485
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament

Cited in

(22)

• Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
• Directed circuits on a torus
• Antidirected Hamiltonian paths between specified vertices of a tournament
• Cycles of all lengths in arc-3-cyclic semicomplete digraphs
• Weakly hamiltonian-connected vertices in bipartite tournaments
• Quasi-hamiltonian paths in semicomplete multipartite digraphs
• A polynomial algorithm determining cyclic vertex connectivity of \(k\)-regular graphs with fixed \(k\)
• Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
• scientific article; zbMATH DE number 6004865 (Why is no real title available?)
• Tournaments and Semicomplete Digraphs
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• scientific article; zbMATH DE number 166022 (Why is no real title available?)
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Digraphs with the path‐merging property
• scientific article; zbMATH DE number 1439485 (Why is no real title available?)
• Spanning eulerian subdigraphs in semicomplete digraphs
• Good orientations of unions of edge‐disjoint spanning trees
• Detours in directed graphs
• NC algorithms for antidirected hamiltonian paths and cycles in tournaments
• Strong arc decompositions of split digraphs
• Generalized paths and cycles in semicomplete multipartite digraphs
• The complexity of color-constrained paths in semicomplete multipartite digraphs

This page was built for publication: A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990618)