Publication:3165953

DOI10.4230/LIPIcs.FSTTCS.2008.1747zbMath1248.68059MaRDI QIDQ3165953

Chandra Chekuri, Nitish Korula

Publication date: 19 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_9eb3.html

zbMATH Keywords

approximation; network design; vertex connectivity; rent-or-buy; buy-at-bulk

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C40: Connectivity

Related Items

Unnamed Item, Approximating fault-tolerant group-Steiner problems, A note on Rooted Survivable Networks, A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems