The minimum spanning strong subdigraph problem is fixed parameter tractable
From MaRDI portal
Publication:1005234
DOI10.1016/j.dam.2007.12.003zbMath1169.05327OpenAlexW2103623190MaRDI QIDQ1005234
Anders Yeo, Jörgen Bang-Jensen
Publication date: 9 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.12.003
Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (9)
Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Minimum Leaf Out-Branching Problems ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs ⋮ Minimum leaf out-branching and related problems ⋮ Path-Contractions, Edge Deletions and Connectivity Preservation ⋮ Basic Terminology, Notation and Results ⋮ Locally Semicomplete Digraphs and Generalizations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs
- On strongly connected digraphs with bounded cycle length
- Parametrized complexity theory.
- The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs
- An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
- Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
- Approximating the Minimum Equivalent Digraph
- The Transitive Reduction of a Directed Graph
- Transitive compaction in parallel via branchings
This page was built for publication: The minimum spanning strong subdigraph problem is fixed parameter tractable
