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.004MaRDI QIDQ990080zbMATHOpenAlexFDO

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

zbMATH Keywords

graph algorithmsdirected graphpackingarborescence

Mathematics Subject Classification ID

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

Recommendations

• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Arc-disjoint in-trees in directed graphs
• Disjoint paths in arborescences
• Arc-disjoint in- and out-branchings with the same root in locally semicomplete digraphs
• Covering Directed Graphs by In-Trees

Cites work

• scientific article; zbMATH DE number 5764893 (Why is no real title available?)
• A faster algorithm for finding edge-disjoint branchings
• A good algorithm for edge-disjoint branching
• A matroid approach to finding edge connectivity and packing arborescences
• A note on disjoint arborescences
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Arc-disjoint in-trees in directed graphs
• Combinatorial optimization. Theory and algorithms
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• On two minimax theorems in graph
• Variations for Lovász’ Submodular Ideas

Cited in

(9)

• Precedence-constrained arborescences
• Covering directed graphs by in-trees
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Arc-disjoint out- and in-branchings in compositions of digraphs
• Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs
• Covering Directed Graphs by In-Trees
• Acyclic digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• Arc-disjoint paths and trees in 2-regular 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)