Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

DOI10.1007/11830924_16MaRDI QIDQ3595372zbMATH OpenOpenAlexFDO

Authors Mohammad Salavatipour, Mohammad T. Hajiaghayi, Guy Kortsarz

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_16

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• Approximating the weight of shallow Steiner trees
• scientific article; zbMATH DE number 1834686
• Approximations for a bottleneck Steiner tree problem
• Optimal and approximate bottleneck Steiner trees
• scientific article; zbMATH DE number 1424548
• scientific article; zbMATH DE number 2044939
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees

Cited in

(9)

• One tree suffices: a simultaneous \(O(1)\)-approximation for single-sink buy-at-bulk
• Network design problems with bounded distances via shallow-light Steiner trees
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• Approximating Some Network Design Problems with Node Costs
• Brief announcement: Characterizing demand graphs for (fixed-parameter) shallow-light Steiner network
• Approximating some network design problems with node costs

This page was built for publication: Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

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