The complexity of finding arc-disjoint branching flows

DOI10.1016/J.DAM.2015.10.012MaRDI QIDQ298947zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• (Arc-)disjoint flows in networks
• Balanced branchings in digraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• Matroid theory and its applications in electric network theory and in statics
• Network flows. Theory, algorithms, and applications.
• On covering intersecting set-systems by digraphs
• On the directed degree-preserving spanning tree problem
• On two minimax theorems in graph
• Sur les arborescences dans un graphe oriente
• Which problems have strongly exponential complexity?

Cited in

(9)

• From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows
• Arc-disjoint paths and trees in 2-regular digraphs
• 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
• (Arc-)disjoint flows in networks

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)