{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:10:37Z","timestamp":1768108237524,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540939795","type":"print"},{"value":"9783540939801","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-540-93980-1_3","type":"book-chapter","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T05:12:21Z","timestamp":1231737141000},"page":"29-42","source":"Crossref","is-referenced-by-count":12,"title":["Degree-Constrained Subgraph Problems: Hardness and Approximation Results"],"prefix":"10.1007","author":[{"given":"Omid","family":"Amini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"P\u00e9rennes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"7","key":"3_CR1","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1016\/j.dam.2007.05.059","volume":"156","author":"L. Addario-Berry","year":"2008","unstructured":"Addario-Berry, L., Dalal, K., Reed, B.: Degree constrained subgraphs. Discrete Appl. Math.\u00a0156(7), 1168\u20131174 (2008)","journal-title":"Discrete Appl. Math."},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Proc. 26th ACM Symp. on Theory of Computing, New York, USA, pp. 326\u2013335 (1994)","DOI":"10.1145\/195058.195179"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Amini, O., Peleg, D., P\u00e9rennes, S., Sau, I., Saurabh, S.: Degree-Constrained Subgraph Problems: Hardness and Approximation Results. Technical Report 6690, INRIA, Accessible in Ignasi Sau\u2019s homepage (2008)","DOI":"10.1007\/978-3-540-93980-1_3"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-540-77120-3_49","volume-title":"Algorithms and Computation","author":"O. Amini","year":"2007","unstructured":"Amini, O., P\u00e9rennes, S., Sau, I.: Hardness and Approximation of Traffic Grooming. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 561\u2013573. Springer, Heidelberg (2007)"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-540-79723-4_4","volume-title":"Parameterized and Exact Computation","author":"O. Amini","year":"2008","unstructured":"Amini, O., Sau, I., Saurabh, S.: Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 13\u201329. Springer, Heidelberg (2008)"},{"issue":"6","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1395","DOI":"10.1137\/S0097539702416761","volume":"32","author":"A. Bj\u00f6rklund","year":"2003","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Finding a Path of Superlogarithmic Length. SIAM J. on Computing\u00a032(6), 1395\u20131402 (2003)","journal-title":"SIAM J. on Computing"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Demaine, E., Hajiaghayi, M., Kawarabayashi, K.C.: Algorithmic Graph Minor Theory: Decomposition, Approximation and Coloring. In: Proc. 46th IEEE Symp. on Foundations of Computer Science, pp. 637\u2013646 (October 2005)","DOI":"10.1109\/SFCS.2005.14"},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90162-B","volume":"85","author":"P. Erd\u0151s","year":"1990","unstructured":"Erd\u0151s, P., Faudree, R., Rousseau, C.C., Schelp, R.H.: Subgraphs of minimal degree k. Discrete Math.\u00a085(1), 53\u201358 (1990)","journal-title":"Discrete Math."},{"issue":"3","key":"3_CR9","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The Dense k-Subgraph Problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"3_CR10","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree spanning tree to within one from the optimal degree. In: Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, USA, pp. 317\u2013324 (1992)"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms, 409\u2013423 (1994)","DOI":"10.1006\/jagm.1994.1042"},{"key":"3_CR12","first-page":"448","volume-title":"Proc. 15th ACM Symp. on Theory of Computing","author":"H. Gabow","year":"1983","unstructured":"Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proc. 15th ACM Symp. on Theory of Computing, USA, pp. 448\u2013456. ACM Press, New York (1983)"},{"key":"3_CR13","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. W.H. Freeman, San Francisco (1979)"},{"issue":"1","key":"3_CR14","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D. Karger","year":"1997","unstructured":"Karger, D., Motwani, R., Ramkumar, G.: On approximating the longest path in a graph. Algorithmica\u00a018(1), 82\u201398 (1997)","journal-title":"Algorithmica"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proc. 45th IEEE Symp. on Foundations of Computer Science, pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"key":"3_CR16","series-title":"Annals of Discrete Math","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.: Matching Theory. Annals of Discrete Math, vol.\u00a029. North-Holland, Amsterdam (1986)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Lund, C., Yannakakis, M.: The Approximation of Maximum Subgraph Problems. In: Proc. 20th Int. Colloq. on Automata, Languages, and Programming (1993)","DOI":"10.1007\/3-540-56939-1_60"},{"issue":"3","key":"3_CR18","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J. Munro","year":"2001","unstructured":"Munro, J., Raman, V.: Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. on Computing\u00a031(3), 762\u2013776 (2001)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C., 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"},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s00453-001-0038-2","volume":"31","author":"R. Ravi","year":"2001","unstructured":"Ravi, R., Marathe, M., Ravi, S., Rosenkrantz, D., Hunt III, H.B.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica\u00a031(1), 58\u201378 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"583","DOI":"10.2307\/1969046","volume":"49","author":"O. Richard","year":"1948","unstructured":"Richard, O.: The Number of Trees. Annals of Mathematics, Second Series\u00a049(3), 583\u2013599 (1948)","journal-title":"Annals of Mathematics, Second Series"}],"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-540-93980-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T05:17:04Z","timestamp":1558070224000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-93980-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540939795","9783540939801"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-93980-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}