{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:11:02Z","timestamp":1743045062786,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642183805"},{"type":"electronic","value":"9783642183812"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-18381-2_39","type":"book-chapter","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T16:01:51Z","timestamp":1294156911000},"page":"467-481","source":"Crossref","is-referenced-by-count":0,"title":["On Approximating the d-Girth of a Graph"],"prefix":"10.1007","author":[{"given":"David","family":"Peleg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mordechai","family":"Shalom","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"7","key":"39_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.A.: Degree constrained subgraphs. Discrete Applied Mathematics\u00a0156(7), 1168\u20131174 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"39_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-93980-1_3","volume-title":"Approximation and Online Algorithms","author":"O. Amini","year":"2009","unstructured":"Amini, O., Peleg, D., P\u00e9rennes, S., Sau, I., Saurabh, S.: Degree-Constrained Subgraph Problems: Hardness and Approximation Results. In: Bampis, E., Skutella, M. (eds.) ALGO\/WAOA 2008. LNCS, vol.\u00a05426, pp. 29\u201342. Springer, Heidelberg (2009), www.cs.technion.ac.il\/~ignasi\/Pubs\/APP+10.pdf"},{"issue":"38-40","key":"39_CR3","doi-asserted-by":"publisher","first-page":"3751","DOI":"10.1016\/j.tcs.2009.04.028","volume":"410","author":"O. Amini","year":"2009","unstructured":"Amini, O., P\u00e9rennes, S., Sau, I.: Hardness and Approximation of Traffic Grooming. Theoretical Computer Science\u00a0410(38-40), 3751\u20133760 (2009)","journal-title":"Theoretical Computer Science"},{"key":"39_CR4","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), www.cs.technion.ac.il\/~ignasi\/Pubs\/ASS10.pdf"},{"issue":"1","key":"39_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of the ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"issue":"4","key":"39_CR6","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1137\/0402039","volume":"2","author":"J.-C. Bermond","year":"1989","unstructured":"Bermond, J.-C., Peyrat, C.: Induced Subgraphs of the Power of a Cycle. SIAM Journal on Discrete Mathematics\u00a02(4), 452\u2013455 (1989)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"39_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(89)90077-0","volume":"75","author":"B. Bollob\u00e1s","year":"1989","unstructured":"Bollob\u00e1s, B., Brightwell, G.: Long Cycles in Graphs with no Subgraphs of Minimal Degree 3. Discrete Mathematics\u00a075, 47\u201353 (1989)","journal-title":"Discrete Mathematics"},{"key":"39_CR8","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Thurimella, R.: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract). In: Proc. of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 292\u2013301 (1996)","DOI":"10.1109\/SFCS.1996.548488"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1002\/net.20029","volume":"44","author":"T. Chow","year":"2004","unstructured":"Chow, T., Lin, P.J.: The ring grooming problem. Networks\u00a044, 194\u2013202 (2004)","journal-title":"Networks"},{"key":"39_CR10","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, vol.\u00a0173. Springer, Heidelberg (2005)"},{"key":"39_CR11","unstructured":"Dorn, F.: Planar Subgraph Isomorphism Revisited. In: Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol.\u00a05, pp. 263\u2013274 (2010)"},{"key":"39_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"B","key":"39_CR13","first-page":"195","volume":"25","author":"P. Erd\u0151s","year":"1988","unstructured":"Erd\u0151s, P., Faudree, R.J., Gy\u00e1rf\u00e1s, A., Schelp, R.H.: Cycles in Graphs Without Proper Subgraphs of Minimum Degree 3. Ars Combinatorica\u00a025(B), 195\u2013201 (1988)","journal-title":"Ars Combinatorica"},{"issue":"1","key":"39_CR14","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.J., Rousseau, C.C., Schelp, R.H.: Subgraphs of Minimal Degree k. Discrete Mathematics\u00a085(1), 53\u201358 (1990)","journal-title":"Discrete Mathematics"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. In: Proc. of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"issue":"4","key":"39_CR16","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal on Applied Mathematics\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"1","key":"39_CR17","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":"39_CR18","unstructured":"K\u00e9zdy, A.: Studies in Connectivity. PhD thesis, Univ. of Illinois, Urbana-Champaign (1991)"},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-48224-5_36","volume-title":"Automata, Languages and Programming","author":"Z. Li","year":"2001","unstructured":"Li, Z., Nakano, S.-I.: Efficient generation of plane triangulations without repetitions. In: Yu, Y., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 433\u2013443. Springer, Heidelberg (2001)"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"39_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-540-85363-3_18","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Z. Nutov","year":"2008","unstructured":"Nutov, Z.: Approximating Directed Weighted-Degree Constrained Networks. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 219\u2013232. Springer, Heidelberg (2008)"},{"key":"39_CR22","unstructured":"Peleg, D., Sau, I., Shalom, M.: On approximating the d-girth of a graph (manuscript), www.lirmm.fr\/~au\/Pubs\/d-girth.pdf"},{"key":"39_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-540-85363-3_19","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"M. Safari","year":"2008","unstructured":"Safari, M., Salavatipour, M.R.: A Constant Factor Approximation for Minimum \u03bb-Edge-Connected k-Subgraph with Metric Costs. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 233\u2013246. Springer, Heidelberg (2008)"},{"key":"39_CR24","doi-asserted-by":"publisher","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"W.T. Tutte","year":"1962","unstructured":"Tutte, W.T.: A census of planar triangulations. Canadian Journal of Mathematics\u00a014, 21\u201338 (1962)","journal-title":"Canadian Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2011: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18381-2_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T11:23:39Z","timestamp":1740828219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18381-2_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642183805","9783642183812"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18381-2_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}