A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
From MaRDI portal
Publication:4018846
DOI10.1137/0405027zbMath0759.05041MaRDI QIDQ4018846
Carsten Thomassen, Jörgen Bang-Jensen
Publication date: 16 January 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0405027
tournaments; polynomial algorithms; feedback vertex set; NP- completeness; semicomplete digraphs; 2-path problem; feedback arcset
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C20: Directed graphs (digraphs), tournaments
05C40: Connectivity
Related Items
On the structure of locally semicomplete digraphs, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Cycles through \(k\) vertices in bipartite tournaments, A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian, On \(k\)-strong and \(k\)-cyclic digraphs