The complexity of finding arc-disjoint branching flows

DOI10.1016/J.DAM.2015.10.012zbMATH Open1339.05371OpenAlexW2181756921MaRDI QIDQ298947FDOQ298947

Authors: Frédéric Havet, A. Yeo, Jørgen Bang-Jensen 

Publication date: 21 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.012

Recommendations

• (Arc-)disjoint flows in networks
• Arc-disjoint paths and trees in 2-regular digraphs
• Arc-disjoint spanning sub(di)graphs in digraphs
• Parameterized algorithms for non-separating trees and branchings in digraphs
• The root location problem for arc-disjoint arborescences

zbMATH Keywords

NP-completenesspolynomial algorithmbranching flowdisjoint branchings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph polynomials (05C31) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network design and communication in computer systems (68M10)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Which problems have strongly exponential complexity?
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Digraphs
• Matroid theory and its applications in electric network theory and in statics
• Sur les arborescences dans un graphe oriente
• On two minimax theorems in graph
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• Balanced branchings in digraphs
• (Arc-)disjoint flows in networks
• On the directed degree-preserving spanning tree problem
• On covering intersecting set-systems by digraphs
• FPT algorithms and kernels for the directed \(k\)-leaf problem

Cited In (6)

• Globally balancing spanning trees
• FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs
• Constrained flows in networks
• Arc-disjoint spanning sub(di)graphs in digraphs
• The root location problem for arc-disjoint arborescences
• Balancing connected colourings of graphs

This page was built for publication: The complexity of finding arc-disjoint branching flows

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