Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs

DOI10.1137/S0895480199354220zbMath1029.05063OpenAlexW2011214451MaRDI QIDQ4443090

Jing Huang, Anders Yeo, Jörgen Bang-Jensen

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480199354220

zbMATH Keywords

Hamiltonian cyclepolynomial algorithmlongest cyclepath factorpath coverquasi-transitive digraphcycle factorextended semicomplete digraphminimum equivalent digraphstrong subdigraph

Mathematics Subject Classification ID

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

Related Items (13)

An algorithmic metatheorem for directed treewidth ⋮ Semicomplete compositions of digraphs ⋮ Sparse Spanning $k$-Connected Subgraphs in Tournaments ⋮ Minimum cycle factors in quasi-transitive digraphs ⋮ Chordality of locally semicomplete and weakly quasi-transitive digraphs ⋮ Longest path partitions in generalizations of tournaments ⋮ Kernels in quasi-transitive digraphs ⋮ The minimum spanning strong subdigraph problem is fixed parameter tractable ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Semicomplete Multipartite Digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions

This page was built for publication: Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs