Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs

DOI10.1016/S0095-8956(02)00020-5zbMath1030.05053OpenAlexW1986322526MaRDI QIDQ1405121

Stéphane Bessy, Steéphan Thomassé

Publication date: 25 August 2003

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0095-8956(02)00020-5

zbMATH Keywords

directed cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

An algorithmic metatheorem for directed treewidth ⋮ The minimum spanning strong subdigraph problem is fixed parameter tractable ⋮ Locally Semicomplete Digraphs and Generalizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• A short proof of the Chen-Manalastas theorem
• Directed cycles with two chords and strong spanning directed subgraphs with few arcs
• Approximating the Minimum Equivalent Digraph

This page was built for publication: Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs