A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
DOI10.1016/J.IPL.2009.09.004zbMATH Open1211.68280OpenAlexW2066173223MaRDI QIDQ990080FDOQ990080
Authors: Kristóf Bérczi, Satoru Fujishige, Naoyuki Kamiyama 
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.004
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A matroid approach to finding edge connectivity and packing arborescences
- On two minimax theorems in graph
- Variations for Lovász’ Submodular Ideas
- A note on disjoint arborescences
- Edge-disjoint in- and out-branchings in tournaments and related path problems
- Combinatorial optimization. Theory and algorithms
- Arc-disjoint in-trees in directed graphs
- A good algorithm for edge-disjoint branching
- A faster algorithm for finding edge-disjoint branchings
- Title not available (Why is that?)
Cited In (9)
- Arc-disjoint paths and trees in 2-regular digraphs
- Arc-disjoint out- and in-branchings in compositions of digraphs
- \(k\)-distinct in- and out-branchings in digraphs
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Precedence-constrained arborescences
- Covering directed graphs by in-trees
- Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs
- Covering Directed Graphs by In-Trees
- Acyclic Digraphs
This page was built for publication: A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990080)
