Additive Guarantees for Degree-Bounded Directed Network Design

DOI10.1137/080734340zbMath1206.68366OpenAlexW2891873695MaRDI QIDQ3586186

Nikhil Bansal, Viswanath Nagarajan, Rohit Khandekar

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/additive-guarantees-for-degreebounded-directed-network-design(3225a3b9-389c-43f1-9def-f55717397456).html

zbMATH Keywords

directed graphsnetwork designapproximation algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

k-Trails: Recognition, Complexity, and Approximations ⋮ On some network design problems with degree constraints ⋮ On generalizations of network design problems with degree bounds ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ A unified algorithm for degree bounded survivable network design ⋮ Colored constrained spanning tree on directed graphs ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Degree bounded matroids and submodular flows ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Degree constrained node-connectivity problems ⋮ The Maximum Binary Tree Problem. ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Simpler analysis of LP extreme points for traveling salesman and survivable network design problems ⋮ Improved approximation algorithms for maximum lifetime problems in wireless networks ⋮ The maximum binary tree problem ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Network-Design with Degree Constraints ⋮ Unnamed Item