Survivable network design: the capacitated minimum spanning network problem

DOI10.1016/J.IPL.2004.04.007MaRDI QIDQ2390307zbMATH OpenOpenAlexFDO

Authors Raja Jothi, Balaji Raghavachari

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.04.007

zbMATH Keywords

2-connectivityaccess network designapproximation algorithmscombinatorial optimization

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Automata, Languages and Programming
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Inapproximability of Survivable Networks
• Inapproximability of survivable networks
• Approximability of capacitated network design

Cites work

• A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem.
• A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
• Automata, Languages and Programming
• Biconnectivity approximations and graph carvings
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• Heuristics with Constant Error Guarantees for the Design of Tree Networks
• scientific article; zbMATH DE number 6472639 (Why is no real title available?)
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• The complexity of the capacitated tree problem

Cited in

(6)

• The \((K, k)\)-capacitated spanning tree problem
• Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• The minimum spanning k-core problem with bounded CVaR under probabilistic edge failures
• The capacitated m two node survivable star problem
• Robust capacitated Steiner trees and networks with uniform demands

This page was built for publication: Survivable network design: the capacitated minimum spanning network problem

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