{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:16:43Z","timestamp":1740097003380,"version":"3.37.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_11","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:53:00Z","timestamp":1402419180000},"page":"120-131","source":"Crossref","is-referenced-by-count":5,"title":["Approximability of Connected Factors"],"prefix":"10.1007","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. S.","family":"Rahul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(logn\/loglogn)-approximation algorithm for the asymmetric traveling salesman problem. In: Proc. of the 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 379\u2013389. SIAM (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Baburin, A.E., Gimadi, E.K.: Approximation algorithms for finding a maximum-weight spanning connected subgraph with given vertex degrees. In: Operations Research Proceedings 2004, pp. 343\u2013351 (2005)","DOI":"10.1007\/3-540-27679-3_43"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Baburin, A.E., Gimadi, E.K.: Polynomial algorithms for some hard problems of finding connected spanning subgraphs of extreme total edge weight. In: Operations Research Proceedings 2006, pp. 215\u2013220 (2007)","DOI":"10.1007\/978-3-540-69995-8_36"},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1134\/S1990478908020026","volume":"2","author":"A.E. Baburin","year":"2008","unstructured":"Baburin, A.E., Gimadi, E.K.: An approximation algorithm for finding a d-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges. Journal of Applied and Industrial Mathematics\u00a02(2), 155\u2013166 (2008)","journal-title":"Journal of Applied and Industrial Mathematics"},{"issue":"4","key":"11_CR5","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1137\/090746495","volume":"40","author":"Y.H. Chan","year":"2011","unstructured":"Chan, Y.H., Fung, W.S., Lau, L.C., Yung, C.K.: Degree bounded network design with metric costs. SIAM Journal on Computing\u00a040(4), 953\u2013980 (2011)","journal-title":"SIAM Journal on Computing"},{"issue":"1-2","key":"11_CR6","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 Applied Mathematics\u00a027(1-2), 59\u201368 (1990)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"11_CR7","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 k-vertex connected subgraph. SIAM Journal on Computing\u00a032(4), 1050\u20131055 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B. Escoffier","year":"2010","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Journal of Discrete Algorithms\u00a08(1), 36\u201349 (2010)","journal-title":"Journal of Discrete Algorithms"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U., Singh, M.: Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 104\u2013118. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74208-1_8"},{"issue":"4","key":"11_CR10","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1287\/opre.27.4.799","volume":"27","author":"M.L. Fisher","year":"1979","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximation for finding a maximum weight Hamiltonian cycle. Operations Research\u00a027(4), 799\u2013809 (1979)","journal-title":"Operations Research"},{"key":"11_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":"11_CR12","doi-asserted-by":"crossref","unstructured":"Gimadi, E.K., Serdyukov, A.I.: A problem of finding the maximal spanning connected subgraph with given vertex degrees. In: Operations Reserach Proceedings 2000, pp. 55\u201359. Springer (2001)","DOI":"10.1007\/978-3-642-56656-1_9"},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted steiner trees and connected dominating sets. Information and Computation\u00a0150(1), 57\u201374 (1999)","journal-title":"Information and Computation"},{"issue":"4","key":"11_CR14","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.I.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Journal of the ACM\u00a052(4), 602\u2013626 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"11_CR15","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms\u00a021(2), 434\u2013450 (1996)","journal-title":"Journal of Algorithms"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Khuller, S., Raghavachari, B.: Graph connectivity. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_171"},{"issue":"2","key":"11_CR17","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. Journal of the ACM\u00a041(2), 214\u2013235 (1994)","journal-title":"Journal of the ACM"},{"key":"11_CR18","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland Mathematics Studies, vol.\u00a0121. Elsevier (1986)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Marx, D., O\u2019sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms\u00a09(4), 30:1\u201330:35 (2013)","DOI":"10.1145\/2500119"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Paluch, K., Mucha, M., M\u0105dry, A.: A 7\/9 approximation algorithm for the maximum traveling salesman problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 298\u2013311. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_23"},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research\u00a018(1), 1\u201311 (1993)","journal-title":"Mathematics of Operations Research"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proc. of the 39th Ann. Int. Symp. on Theory of Computing (STOC), pp. 661\u2013670. ACM (2007)","DOI":"10.1145\/1250790.1250887"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics\u00a06, 347\u2013352 (1954), http:\/\/dx.doi.org\/10.4153\/CJM-1954-033-3","journal-title":"Canadian Journal of Mathematics"},{"key":"11_CR25","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice-Hall (2001)"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"}],"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-08001-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T04:59:52Z","timestamp":1689310792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}