{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:43:44Z","timestamp":1775054624050,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424932","type":"print"},{"value":"9783540446767","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_31","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T16:43:15Z","timestamp":1179506595000},"page":"368-379","source":"Crossref","is-referenced-by-count":13,"title":["Computing Cycle Covers without Short Cycles"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Siebert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"4","key":"31_CR1","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01302963","volume":"14","author":"M. Ajtai","year":"1994","unstructured":"M. Ajtai. Recursive construction for 3-regular expanders. Combinatorica, 14(4):379\u2013416, 1994.","journal-title":"Combinatorica"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation. Springer, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G. Cornu\u00e9jols","year":"1980","unstructured":"G. Cornu\u00e9jols and W. Pulleyblank. A matching problem with side constraints. Discrete Math., 29:135\u2013159, 1980.","journal-title":"Discrete Math."},{"key":"31_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, trees, and flowers. Canad. J. Math., 17:449\u2013467, 1965.","journal-title":"Canad. J. Math."},{"key":"31_CR5","unstructured":"L. Engebretsen and M. Karpinski. Approximation hardness of TSP with bounded metrics. Technical Report 00-089, Electronic Colloquium on Comput. Complexity (ECCC), 2000."},{"key":"31_CR6","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"31_CR7","unstructured":"R. L. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz, editors. Handbook of Combinatorics, volume 1. Elvsevier, 1995."},{"key":"31_CR8","unstructured":"D. Hartvigsen. An Extension of Matching Theory. PhD thesis, Carnegie-Mellon University, 1984."},{"key":"31_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-48777-8_18","volume-title":"7th Int. Conf. on Integer Programming and Combinatorial Optimization (IPCO)","author":"D. Hartvigsen","year":"1999","unstructured":"D. Hartvigsen. The square-free 2-factor problem in bipartite graphs. In 7th Int. Conf. on Integer Programming and Combinatorial Optimization (IPCO), volume 1620 of Lecture Notes in Comput. Sci., pages 234\u2013241. Springer, 1999."},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"J. H\u00e4stad. Some optimal inapproximability results. In Proc. 29th Ann. Symp. on Theory of Comput. (STOC), pages 1\u201310. ACM, 1997.","DOI":"10.1145\/258533.258536"},{"key":"31_CR11","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju, J. K. Park, and C. Stein. Long tours and short superstrings. In Proc. 35th Ann. Symp. on Foundations of Comput. Sei. (FOCS), pages 166\u2013177. IEEE, 1994.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"31_CR13","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, editors. The Traveling Salesman Problem. Wiley, 1985."},{"key":"31_CR14","unstructured":"L. Lov\u00e1sz and M. D. Plummer. Matching Theory. Elsevier, 1986."},{"key":"31_CR15","unstructured":"Papadimitriou and Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982."},{"issue":"3","key":"31_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. System Set, 43(3):425\u2013440, 1991.","journal-title":"J. Comput. System Set"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Math. Oper. Res., 18:1\u201311, 1993.","journal-title":"Math. Oper. Res."},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W. T. Tutte","year":"1954","unstructured":"W. T. Tutte. A short proof of the factor theorem for finite graphs. Canad. J. Math., 6:347\u2013352, 1954.","journal-title":"Canad. J. Math."},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(92)90103-3","volume":"44","author":"S. Vishwanathan","year":"1992","unstructured":"S. Vishwanathan. An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Process. Lett., 44:297\u2013302, 1992.","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T04:44:12Z","timestamp":1556426652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}