Fast Exact Algorithms for Survivable Network Design with Uniform Requirements

Agrawal, Akanksha and Misra, Pranabendu and Panolan, Fahad and Saurabh, Saket (2022) Fast Exact Algorithms for Survivable Network Design with Uniform Requirements. Algorithmica. ISSN 0178-4617

Full text not available from this repository. (Request a copy)


We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weightλ-connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weightλ-connectivity Augmentation. It is easy to see that a minimum solution to these problems contains at most 2 λ(n- 1) edges. Using this fact one can design a brute-force algorithm which runs in time 2 O(λnlogn), however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2 O(λn), for both undirected and directed networks. Our results are obtained via well known characterizations of λ-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahad
Item Type: Article
Uncontrolled Keywords: Exact algorithms; Network augmentation; Survivable network design
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 19 Jul 2022 09:01
Last Modified: 19 Jul 2022 09:01
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9785 Statistics for this ePrint Item