Parameterized Algorithms to Preserve Connectivity
作者： Manu Basavaraju , Fedor V. Fomin , Petr Golovach , Pranabendu Misra , M. S. Ramanujan
DOI: 10.1007/978-3-662-43948-7_66
关键词:
摘要: We study the following family of connectivity problems. For a given λ-edge connected (multi) graph G = (V,E), set links L such that + (V, E ∪ L) is (λ 1)-edge connected, and positive integer k, questions are
springer.com
sci-hub.st 参考文章(9)
Hiroshi Nagamochi, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree computing and combinatorics conference. ,vol. 126, pp. 31- 40 ,(1999) , 10.1016/S0166-218X(02)00218-4
S. E. Dreyfus, R. A. Wagner, The steiner problem in graphs Networks. ,vol. 1, pp. 195- 207 ,(1971) , 10.1002/NET.3230010302
László A. Végh, Augmenting Undirected Node-Connectivity by One SIAM Journal on Discrete Mathematics. ,vol. 25, pp. 695- 718 ,(2011) , 10.1137/100787507
András Frank, Augmenting Graphs to Meet Edge-Connectivity Requirements SIAM Journal on Discrete Mathematics. ,vol. 5, pp. 25- 53 ,(1992) , 10.1137/0405003
Greg N. Frederickson, Joseph Ja’Ja’, Approximation Algorithms for Several Graph Augmentation Problems SIAM Journal on Computing. ,vol. 10, pp. 270- 283 ,(1981) , 10.1137/0210019
Toshimasa Watanabe, Akira Nakamura, Edge-connectivity augmentation problems Journal of Computer and System Sciences. ,vol. 35, pp. 96- 144 ,(1987) , 10.1016/0022-0000(87)90038-9
Johannes Uhlmann, Jiong Guo, Kernelization and complexity results for connectivity augmentation problems Networks. ,vol. 56, pp. 131- 142 ,(2010) , 10.1002/NET.V56:2
Hans L Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof, Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth Automata, Languages, and Programming. ,vol. 243, pp. 196- 207 ,(2013) , 10.1007/978-3-642-39206-1_17
Dániel Marx, László A. Végh, Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation Automata, Languages, and Programming. pp. 721- 732 ,(2013) , 10.1007/978-3-642-39206-1_61