Approximation to the Minimum Cost Edge Installation Problem

DOI10.1007/978-3-540-77120-3_27MaRDI QIDQ5387765zbMATH OpenOpenAlexFDO

Authors Ehab Morsy, Hiroshi Nagamochi

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_27

zbMATH Keywords

Approximation algorithmGraph algorithmNetwork optimizationRouting problem

Mathematics Subject Classification ID

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

Recommendations

• Approximating capacitated tree-routings in networks
• Approximating the Generalized Capacitated Tree-Routing Problem
• Approximating the single-sink link-installation problem in network design
• Approximating the k-splittable capacitated network design problem
• Approximating Capacitated Tree-Routings in Networks

Cites work

• A constant factor approximation for the single sink edge installation problems
• Approximating the single-sink link-installation problem in network design
• Approximation algorithms for a capacitated network design problem
• Balancing minimum spanning trees and shortest-path trees
• scientific article; zbMATH DE number 1532274 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• Improved Approximation for Single-Sink Buy-at-Bulk

Cited in

(2)

• Approximation schemes for capacitated geometric network design
• Approximation schemes for capacitated geometric network design

This page was built for publication: Approximation to the Minimum Cost Edge Installation Problem

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