An $O(k^3\log n)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
by Julia Chuzhoy and Sanjeev Khanna
Theory of Computing, Volume 8(18), pp. 401-413, 2012
Bibliography with links to cited articles
[1] Ajit Agrawal, Philip Klein, and R. Ravi: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440–456, 1995. Preliminary version in STOC’91. [doi:10.1137/S0097539792236237]
[2] Marshall Bern and Paul Plassmann: The Steiner problem with edge lengths 1 and 2. Inform. Process. Lett., 32(4):171–176, 1989. [doi:10.1016/0020-0190(89)90039-2]
[3] Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna: Network design for vertex connectivity. In Proc. 40th STOC, pp. 167–176. ACM Press, 2008. [doi:10.1145/1374376.1374403]
[4] Chandra Chekuri and Nitish Korula: Single-sink network design with vertex connectivity requirements. In IARCS Ann. Conf. on Foundations of Software Tech. and Theor. Comput. Sci. (FSTTCS’08), pp. 131–142. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2008. [doi:10.4230/LIPIcs.FSTTCS.2008.1747]
[5] Chandra Chekuri and Nitish Korula: A graph reduction step preserving element-connectivity and applications. In Proc. 36th Internat. Colloq. on Automata, Languages and Programming (ICALP’09), pp. 254–265. Springer, 2009. [doi:10.1007/978-3-642-02927-1_22]
[6] Joseph Cheriyan, Santosh Vempala, and Adrian Vetta: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput., 32(4):1050–1055, 2003. Preliminary version in STOC’02. [doi:10.1137/S0097539701392287]
[7] Joseph Cheriyan, Santosh Vempala, and Adrian Vetta: Network design via iterative rounding of setpair relaxations. Combinatorica, 26(3):255–275, 2006. [doi:10.1007/s00493-006-0016-z]
[8] Julia Chuzhoy and Sanjeev Khanna: Algorithms for single-source vertex connectivity. In Proc. 49th FOCS, pp. 105–114. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.63]
[9] Arkadiĭ G. D’yachkov and Vyacheslav V. Rykov: Bounds on the length of disjunctive codes. Probl. Peredachi Inf., 18:7–13, 1982. [Math-Net.ru].
[10] Jittat Fakcharoenphol and Bundit Laekhanukit: An O(log 2k)-approximation algorithm for the k-vertex connected spanning subgraph problem. In Proc. 40th STOC, pp. 153–158. ACM Press, 2008. [doi:10.1145/1374376.1374401]
[11] Lisa Fleischer: A 2-approximation for minimum cost {0, 1, 2} vertex connectivity. In Proc. 8th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’01), pp. 115–129. Springer, 2001. [doi:10.1007/3-540-45535-3_10]
[12] Lisa Fleischer, Kamal Jain, and David P. Williamson: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. System Sci., 72(5):838–867, 2006. Preliminary version in FOCS’01. [doi:10.1016/j.jcss.2005.05.006]
[13] András Frank and Tibor Jordán: Minimal edge-coverings of pairs of sets. J. Combin. Theory Ser. B, 65(1):73–110, 1995. [doi:10.1006/jctb.1995.1044]
[14] Zoltán Füredi: On r-cover-free families. J. Combin. Theory Ser. A, 73(1):172–173, 1996. [doi:10.1006/jcta.1996.0012]
[15] Kamal Jain: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–60, 2001. Preliminary version in FOCS’98. [doi:10.1007/s004930170004]
[16] Kamal Jain, Ion Măndoiu, Vijay V. Vazirani, and David P. Williamson: A primal-dual schema based approximation algorithm for the element connectivity problem. J. Algorithms, 45(1):1–15, 2002. Preliminary version in SODA’99. [doi:10.1016/S0196-6774(02)00222-5]
[17] Guy Kortsarz, Robert Krauthgamer, and James R. Lee: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704–720, 2004. Preliminary version in APPROX’02. [doi:10.1137/S0097539702416736]
[18] Guy Kortsarz and Zeev Nutov: Approximating k-node connected subgraphs via critical graphs. SIAM J. Comput., 35(1):247–257, 2005. Preliminary version in STOC’04. [doi:10.1137/S0097539703435753]
[19] Ravi Kumar, Sridhar Rajagopalan, and Amit Sahai: Coding constructions for blacklisting problems without computational assumptions. In 19th Ann. Internat. Cryptology Conf. (CRYPTO’99), pp. 609–623. Springer, 1999. [doi:10.1007/3-540-48405-1_38]
[20] Yuval Lando and Zeev Nutov: Inapproximability of survivable networks. Theoret. Comput. Sci., 410(21-23):2122–2125, 2009. Preliminary version in APPROX’08. [doi:10.1016/j.tcs.2009.01.036]
[21] Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
[22] Zeev Nutov: An almost O(log k)-approximation for k-connected subgraphs. In Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’09), pp. 912–921. ACM Press, 2009. [ACM:1496770.1496869]
[23] Zeev Nutov: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In Proc. 50th FOCS, pp. 417–426. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.9]
[24] Zeev Nutov: A note on rooted survivable networks. Inform. Process. Lett., 109(19):1114–1119, 2009. [doi:10.1016/j.ipl.2009.07.011]
[25] Douglas R. Stinson, Ruizhong Wei, and Lie Zhu: Some new bounds for cover-free families. J. Combin. Theory Ser. A, 90(1):224–234, 2000. [doi:10.1006/jcta.1999.3036]