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

DOI10.1007/11830924_16zbMATH Open1155.68577OpenAlexW2176619219MaRDI QIDQ3595372FDOQ3595372

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• One tree suffices: a simultaneous \(O(1)\)-approximation for single-sink buy-at-bulk
• Approximating Some Network Design Problems with Node Costs
• 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
• 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)