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.004zbMath1211.68280OpenAlexW2066173223MaRDI QIDQ990080

Naoyuki Kamiyama, Kristóf Bérczi, Satoru Fujishige

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

zbMATH Keywords

packingdirected graphgraph algorithmsarborescence

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Precedence-constrained arborescences, Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs, Arc-disjoint paths and trees in 2-regular digraphs, \(k\)-distinct in- and out-branchings in digraphs, Acyclic Digraphs

Cites Work

• Unnamed Item
• A note on disjoint arborescences
• Arc-disjoint in-trees in directed graphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• A good algorithm for edge-disjoint branching
• On two minimax theorems in graph
• A faster algorithm for finding edge-disjoint branchings
• A matroid approach to finding edge connectivity and packing arborescences
• Variations for Lovász’ Submodular Ideas
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Combinatorial optimization. Theory and algorithms