Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Marx, D. & Végh, L. A.
(2013).
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation.
In
Fomin, F. V., Freivalds, R., Kwiatkowska, M. & Peleg, D.
(Eds.),
Automata, Languages, and Programming: 40th International Colloquium, Icalp 2013, Riga, Latvia, July 8-12, 2013
(pp. 721-732).
Springer Berlin / Heidelberg.
https://doi.org/10.1007/978-3-642-39206-1_61
(2013).
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation.
In
Fomin, F. V., Freivalds, R., Kwiatkowska, M. & Peleg, D.
(Eds.),
Automata, Languages, and Programming: 40th International Colloquium, Icalp 2013, Riga, Latvia, July 8-12, 2013
(pp. 721-732).
Springer Berlin / Heidelberg.
https://doi.org/10.1007/978-3-642-39206-1_61
We consider connectivity-augmentation problems in a setting where each potential new edge has a nonnegative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost. The main result is that the minimum cost augmentation of edge-connectivity from k − 1 to k with at most p new edges is fixed-parameter tractable parameterized by p and admits a polynomial kernel. We also prove the fixed-parameter tractability of increasing edge-connectivity from 0 to 2, and increasing node-connectivity from 1 to 2.