{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:37Z","timestamp":1740109417104,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,11,16]],"date-time":"2016-11-16T00:00:00Z","timestamp":1479254400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001834","name":"University of Twente","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001834","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00224-016-9723-z","type":"journal-article","created":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T05:25:35Z","timestamp":1479360335000},"page":"441-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for Connected Graph Factors of Minimum Weight"],"prefix":"10.1007","volume":"62","author":[{"given":"Kamiel","family":"Cornelissen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruben","family":"Hoeksma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"S. Rahul","sequence":"additional","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,11,16]]},"reference":[{"issue":"4","key":"9723_CR1","doi-asserted-by":"crossref","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":"9723_CR2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0166-218X(90)90129-Z","volume":"27","author":"F Cheah","year":"1990","unstructured":"Cheah, F., Corneil, Derek G.: The complexity of regular subgraph recognition. Discret. Appl. Math. 27(1\u20132), 59\u201368 (1990)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"9723_CR3","doi-asserted-by":"crossref","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 k-vertex connected subgraph. SIAM J. Comput. 32(4), 1050\u20131055 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9723_CR4","doi-asserted-by":"crossref","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. Discret. Math. 21(3), 612\u2013636 (2007)","journal-title":"SIAM J. Discret. Math."},{"key":"9723_CR5","doi-asserted-by":"crossref","unstructured":"Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N S, Rahul, C S: Approximability of connected factors. In: Kaklamanis, C., Pruhs, K. (eds.) Proc. of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013), volume 8447 of Lecture Notes in Computer Science, pp 120\u2013131. Springer (2014)","DOI":"10.1007\/978-3-319-08001-7_11"},{"key":"9723_CR6","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Lingas, A.: Minimum k-connected geometric networks. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp 536\u2013539. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_237"},{"key":"9723_CR7","doi-asserted-by":"crossref","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. Algo. 24(2), 310\u2013324 (1997)","DOI":"10.1006\/jagm.1997.0862"},{"issue":"3","key":"9723_CR8","doi-asserted-by":"crossref","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. Theory Comput. Syst. 45(3), 512\u2013532 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"9723_CR9","doi-asserted-by":"crossref","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. Discret. Optim. 7(4), 246\u2013255 (2010)","journal-title":"Discret. Optim."},{"key":"9723_CR10","doi-asserted-by":"crossref","unstructured":"Fukunaga, T., Ravi, R.: Iterative rounding approximation algorithms for degree-bounded node-connectivity network design. In: Proc. of the 53rd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 263\u2013272. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.30"},{"key":"9723_CR11","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)"},{"key":"9723_CR12","doi-asserted-by":"crossref","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":"9723_CR13","doi-asserted-by":"crossref","unstructured":"Kammer, F., T\u00e4ubig, H.: Connectivity. In: Brandes, U., Erlebach, T. (eds.) Network Analysis: Methodological Foundations, volume 3418 of Lecture Notes in Computer Science, pp 143\u2013177. Springer (2005)","DOI":"10.1007\/978-3-540-31955-9_7"},{"issue":"5","key":"9723_CR14","doi-asserted-by":"crossref","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":"9723_CR15","doi-asserted-by":"crossref","unstructured":"Khuller, S., Raghavachari, B.: Graph connectivity. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp 371\u2013373. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_171"},{"issue":"2","key":"9723_CR16","doi-asserted-by":"crossref","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":"9723_CR17","doi-asserted-by":"crossref","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":"9723_CR18","doi-asserted-by":"crossref","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":"9723_CR19","doi-asserted-by":"crossref","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":"9723_CR20","doi-asserted-by":"crossref","unstructured":"Lau, L C, Zhou, H: A unified algorithm for degree bounded survivable network design. In: Lee, J., Vygen, J. (eds.) Proc. of the 17th Int. Conf. on Integer Programming and Combinatorial Optimization (IPCO), volume 8494 of Lecture Notes in Computer Science, pp 369\u2013380. Springer (2014)","DOI":"10.1007\/978-3-319-07557-0_31"},{"key":"9723_CR21","unstructured":"Lov\u00e1sz, L, Plummer, M D.: Matching Theory, volume 121 of North-Holland Mathematics Studies. Elsevier (1986)"},{"key":"9723_CR22","doi-asserted-by":"crossref","unstructured":"Manthey, B, Waanders, M: Approximation algorithms for k-connected graph factors. In: Sanit\u00e1, L., Skutella, M (eds.) Proc. of the 13th Workshop on Approximation and Online Algorithms (WAOA 2015), volume 9499 of Lecture Notes in Computer Science, pp 1\u201312. Springer (2016)","DOI":"10.1007\/978-3-319-28684-6_1"},{"key":"9723_CR23","doi-asserted-by":"crossref","unstructured":"Narayanaswamy, N. S., Rahul, C. S.: Approximation and exact algorithms for special cases of connected f-factors. Proc. of the 10th Int. Computer Science Symp. in Russia (CSR), volume 9139 of Lecture Notes in Computer Science, pp. 350\u2013363. Springer (2015)","DOI":"10.1007\/978-3-319-20297-6_23"},{"issue":"3","key":"9723_CR24","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., Yannakakis, M: Optimization approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9723_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C. H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9723_CR26","doi-asserted-by":"crossref","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":"9723_CR27","doi-asserted-by":"crossref","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":"9723_CR28","unstructured":"West, D B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall (2001)"},{"key":"9723_CR29","doi-asserted-by":"crossref","unstructured":"Williamson, DP., Shmoys, DB.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"key":"9723_CR30","doi-asserted-by":"crossref","unstructured":"Wolsey, L. A.: Heuristic analysis, linear programming and branch and bound. In: Rayward-Smith, V. J. (ed.) Combinatorial Optimization II, volume 13 of Mathematical Programming Studies, pp 121\u2013134. Springer (1980)","DOI":"10.1007\/BFb0120913"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9723-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9723-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9723-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T13:58:43Z","timestamp":1568555923000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9723-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,16]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9723"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9723-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,11,16]]}}}