Additive guarantees for degree-bounded directed network design

DOI10.1137/080734340MaRDI QIDQ3586186zbMATH OpenOpenAlexFDO

Authors N. Bansal, Rohit Khandekar, Viswanath Nagarajan

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

approximation algorithmsdirected graphsnetwork design

Mathematics Subject Classification ID

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

Recommendations

• Additive Approximation for Bounded Degree Survivable Network Design
• Degree bounded network design with metric costs
• Approximating Directed Weighted-Degree Constrained Networks
• Algorithms for a network design problem with crossing supermodular demands

Cited in

(29)

• Chain-constrained spanning trees
• Refuting a conjecture of goemans on bounded degree spanning trees
• Binary Steiner trees: structural results and an exact solution approach
• \(k\)-trails: recognition, complexity, and approximations
• The maximum binary tree problem
• Bounded-degree light approximate shortest-path trees in doubling metrics
• Degree bounded matroids and submodular flows
• Bi-criteria and approximation algorithms for restricted matchings
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Network-design with degree constraints
• \(k\)-trails: recognition, complexity, and approximations
• Approximating Directed Weighted-Degree Constrained Networks
• On some network design problems with degree constraints
• Network design with weighted degree constraints
• Degree constrained node-connectivity problems
• Multicommodity flow in trees: packing via covering and iterated relaxation
• Additive Approximation for Bounded Degree Survivable Network Design
• Matroidal degree-bounded minimum spanning trees
• The Maximum Binary Tree Problem.
• Approximate multi-matroid intersection via iterative refinement
• Colored constrained spanning tree on directed graphs
• Approximating directed weighted-degree constrained networks
• Fast combinatorial algorithms for efficient sortation
• Improved approximation algorithms for maximum lifetime problems in wireless networks
• Fast combinatorial algorithms for efficient sortation
• Tight guarantees for cut-relative survivable network design via a decomposition technique
• On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
• A unified algorithm for degree bounded survivable network design
• Simpler analysis of LP extreme points for traveling salesman and survivable network design problems

This page was built for publication: Additive guarantees for degree-bounded directed network design

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