A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
From MaRDI portal
Publication:4018846
DOI10.1137/0405027zbMath0759.05041OpenAlexW2023138157MaRDI 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
tournamentspolynomial algorithmsfeedback vertex setNP- completenesssemicomplete digraphs2-path problemfeedback arcset
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) Connectivity (05C40)
Related Items
Cycles through \(k\) vertices in bipartite tournaments, Design and serial construction of digraph braids, Unnamed Item, Feedback arc set in bipartite tournaments is NP-complete, A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian, On \(k\)-strong and \(k\)-cyclic digraphs, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Hardness of fully dense problems, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Edge-disjoint in- and out-branchings in tournaments and related path problems, Component order connectivity in directed graphs, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number, Safe sets and in-dominating sets in digraphs, NC algorithms for antidirected hamiltonian paths and cycles in tournaments, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Disjoint paths in unions of tournaments, Disjoint paths in tournaments, On the structure of locally semicomplete digraphs, Component order connectivity in directed graphs, DAG-Width and Circumference of Digraphs, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, On width measures and topological problems on semi-complete digraphs, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Linkages in locally semicomplete digraphs and quasi-transitive digraphs, Tournaments and Semicomplete Digraphs, Quasi-Transitive Digraphs and Their Extensions, Cycle Transversals in Tournaments with Few Vertex Disjoint Cycles, Disjoint Paths in Decomposable Digraphs
