Balanced branchings in digraphs

DOI10.1016/J.TCS.2015.06.026MaRDI QIDQ2354769zbMATH OpenOpenAlexFDO

Authors A. Yeo, Jørgen Bang-Jensen

Publication date 24 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.026

zbMATH Keywords

balancing degreesbalancing verticesbranchingsNP-completeout-treespolynomial algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 7378329
• The \(b\)-branching problem in digraphs
• Finding minimal branchings with a given number of arcs
• Branching in digraphs with many and few leaves: structural and algorithmic results
• Arc-disjoint paths and trees in 2-regular digraphs

Cites work

• (Arc-)disjoint flows in networks
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• Digraphs
• FPT algorithms and kernels for the directed k-leaf problem
• Highly connected non-2-linked digraphs
• Minimum Leaf Out-Branching Problems
• On the directed degree-preserving spanning tree problem
• Small degree out‐branchings
• Sur les arborescences dans un graphe oriente
• Which problems have strongly exponential complexity?

Cited in

(7)

• Branching on a Sierpinski graph
• The \(b\)-branching problem in digraphs
• The complexity of finding arc-disjoint branching flows
• Finding minimal branchings with a given number of arcs
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)
• FPT algorithms for packing k-safe spanning rooted sub(di)graphs
• Constrained flows in networks

This page was built for publication: Balanced branchings in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354769)