{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:09:23Z","timestamp":1726409363454},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286839"},{"type":"electronic","value":"9783319286846"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_1","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T05:32:03Z","timestamp":1452576723000},"page":"1-12","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for k-Connected Graph Factors"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marten","family":"Waanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1137\/090746495","volume":"40","author":"YH Chan","year":"2011","unstructured":"Chan, Y.H., Fung, W.S., Lau, L.C., Yung, C.K.: Degree bounded network design with metric costs. SIAM J. Comput. 40(4), 953\u2013980 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"1_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0166-218X(90)90129-Z","volume":"27","author":"F Cheah","year":"1990","unstructured":"Cheah, F., Corneil, D.G.: The complexity of regular subgraph recognition. Discrete Appl. Math. 27(1\u20132), 59\u201368 (1990)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1137\/S0097539701392287","volume":"32","author":"J Cheriyan","year":"2003","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -vertex connected subgraph. SIAM J. Comput. 32(4), 1050\u20131055 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1_CR4","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1137\/040621806","volume":"21","author":"J Cheriyan","year":"2007","unstructured":"Cheriyan, J., Vetta, A.: Approximation algorithms for network design with metric costs. SIAM J. Discrete Math. 21(3), 612\u2013636 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-319-08001-7_11","volume-title":"Approximation and Online Algorithms","author":"K Cornelissen","year":"2014","unstructured":"Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N.S., Rahul, C.S.: Approximability of connected factors. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 120\u2013131. Springer, Heidelberg (2014)"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-0-387-30162-4_237","volume-title":"Encyclopedia of Algorithms","author":"A Czumaj","year":"2008","unstructured":"Czumaj, A., Lingas, A.: Minimum \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -connected geometric networks. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 536\u2013539. Springer, Heidelberg (2008)"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jagm.1997.0862","volume":"24","author":"SP Fekete","year":"1997","unstructured":"Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.E.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24(2), 310\u2013324 (1997)","journal-title":"J. Algorithms"},{"issue":"3","key":"1_CR8","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/s00224-008-9149-3","volume":"45","author":"T Fukunaga","year":"2009","unstructured":"Fukunaga, T., Nagamochi, H.: Network design with edge-connectivity and degree constraints. Theor. Comput. Syst. 45(3), 512\u2013532 (2009)","journal-title":"Theor. Comput. Syst."},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.disopt.2010.05.004","volume":"7","author":"T Fukunaga","year":"2010","unstructured":"Fukunaga, T., Nagamochi, H.: Network design with weighted degree constraints. Discrete Optim. 7(4), 246\u2013255 (2010)","journal-title":"Discrete Optim."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Fukunaga, T., Ravi, R.: Iterative rounding approximation algorithms for degree-bounded node-connectivity network design. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 263\u2013272. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.30"},{"key":"1_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"MX Goemans","year":"1993","unstructured":"Goemans, M.X., Bertsimas, D.: Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60, 145\u2013166 (1993)","journal-title":"Math. Program."},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-540-31955-9_7","volume-title":"Network Analysis","author":"F Kammer","year":"2005","unstructured":"Kammer, F., T\u00e4ubig, H.: Connectivity. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 143\u2013177. Springer, Heidelberg (2005)"},{"issue":"5","key":"1_CR14","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1016\/j.jcss.2013.01.019","volume":"79","author":"R Khandekar","year":"2013","unstructured":"Khandekar, R., Kortsarz, G., Nutov, Z.: On some network design problems with degree constraints. J. Comput. Syst. Sci. 79(5), 725\u2013736 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-0-387-30162-4_171","volume-title":"Encyclopedia of Algorithms","author":"S Khuller","year":"2008","unstructured":"Khuller, S., Raghavachari, B.: Graph connectivity. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 371\u2013373. Springer, Heidelberg (2008)"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM 41(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00453-003-1027-4","volume":"37","author":"G Kortsarz","year":"2003","unstructured":"Kortsarz, G., Nutov, Z.: Approximating node connectivity problems via set covers. Algorithmica 37(2), 75\u201392 (2003)","journal-title":"Algorithmica"},{"issue":"3","key":"1_CR18","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"LC Lau","year":"2009","unstructured":"Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1_CR19","doi-asserted-by":"publisher","first-page":"2217","DOI":"10.1137\/110854461","volume":"42","author":"LC Lau","year":"2013","unstructured":"Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. SIAM J. Comput. 42(6), 2217\u20132242 (2013)","journal-title":"SIAM J. Comput."},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-319-07557-0_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"LC Lau","year":"2014","unstructured":"Lau, L.C., Zhou, H.: A unified algorithm for degree bounded survivable network design. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 369\u2013380. Springer, Heidelberg (2014)"},{"key":"1_CR21","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, North-Holland Mathematics Studies, vol. 121. Elsevier (1986)"},{"issue":"1","key":"1_CR22","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2629366","volume":"62","author":"M Singh","year":"2015","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM 62(1), 1:1\u20131:19 (2015)","journal-title":"J. ACM"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"1_CR24","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Upper Saddle River (2001)","edition":"2"},{"key":"1_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2011)"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0120913","volume-title":"Combinatorial Optimization II, Mathematical Programming Studies","author":"LA Wolsey","year":"1980","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II, Mathematical Programming Studies, vol. 13, pp. 121\u2013134. Springer, Heidelberg (1980)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T06:14:05Z","timestamp":1559369645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}