Minimum \(k\) arborescences with bandwidth constraints

DOI10.1007/s00453-003-1054-1zbMath1053.05109OpenAlexW2166763236MaRDI QIDQ1879251

Xiaotie Deng, Lusheng Wang, Mao-cheng Cai

Publication date: 22 September 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1054-1

zbMATH Keywords

digraphmatroidmaximum flowarborescencealgorithm complexitypolymatroid intersection

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20)

Related Items

Edge-bandwidth of grids and tori ⋮ Precedence-constrained arborescences ⋮ A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem ⋮ On routing in VLSI design and communication networks ⋮ Packing trees in communication networks

Cites Work

• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Geometric algorithms and combinatorial optimization
• On two minimax theorems in graph
• Blocking, antiblocking, and pairs of matroids and polymatroids
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• A weighted matroid intersection algorithm
• Routing to Multiple Destinations in Computer Networks
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Minimum \(k\) arborescences with bandwidth constraints