{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:08Z","timestamp":1760202608411},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_53","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T13:06:19Z","timestamp":1267535179000},"page":"641-653","source":"Crossref","is-referenced-by-count":10,"title":["Cycle Cover with Short Cycles"],"prefix":"10.1007","author":[{"given":"Nicole","family":"Immorlica","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Mahdian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahab S.","family":"Mirrokni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Blaser, M., Siebert, B.: Computing cycle covers without short cycles. In: Proceedings of the 34th Annual European Symposium of Algorithms (2001)","key":"53_CR1","DOI":"10.1007\/3-540-44676-1_31"},{"key":"53_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.: Matching euler tours and the chinese postman problem. Mathematical programming\u00a05, 88\u2013124 (1973)","journal-title":"Mathematical programming"},{"unstructured":"Ergun, O., Kuyzu, G., Savelsbergh, M.: Collaborative logistics: The shipper collaboration problem. Submitted to Computers and Operations Research Odysseus 2003 Special Issue (2003)","key":"53_CR3"},{"unstructured":"Ergun, O., Kuyzu, G., Savelsbergh, M.: The lane covering problem (2003) (manuscript)","key":"53_CR4"},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045, 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"53_CR6","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company, New York (1979)"},{"issue":"3","key":"53_CR7","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1137\/S089548019325232X","volume":"9","author":"O. Goldschmidt","year":"1996","unstructured":"Goldschmidt, O., Hochbaum, D., Hurkens, C., Yu, G.: Approximation algorithms for the k-clique covering problem. SIAM Journal of Discrete Math.\u00a09(3), 492\u2013509 (1996)","journal-title":"SIAM Journal of Discrete Math."},{"key":"53_CR8","first-page":"273","volume":"1","author":"M. Guan","year":"1962","unstructured":"Guan, M.: Graphic programming using odd and even points. Chinese Mathematics\u00a01, 273\u2013277 (1962)","journal-title":"Chinese Mathematics"},{"issue":"2","key":"53_CR9","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1287\/ijoc.13.2.104.10516","volume":"13","author":"D. Hochbaum","year":"2001","unstructured":"Hochbaum, D., Olinick, E.: The bounded cycle-cover problem. INFORMS Journal on Computing\u00a013(2), 104\u2013119 (2001)","journal-title":"INFORMS Journal on Computing"},{"key":"53_CR10","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"Holyer","year":"1981","unstructured":"Holyer: The np-completeness of some edge partitioning problems. SIAM journal of Computing\u00a010, 713\u2013717 (1981)","journal-title":"SIAM journal of Computing"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"746","DOI":"10.1137\/0210058","volume":"10","author":"A. Itai","year":"1981","unstructured":"Itai, A., Lipton, R.J., Papadimitriou, C.H., Rodeh, M.: Covering graphs by simple circuits. SIAM Journal on Computing\u00a010, 746\u2013750 (1981)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"53_CR12","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K. Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. Journal of the ACM\u00a050(6), 795\u2013824 (2003)","journal-title":"Journal of the ACM"},{"issue":"2","key":"53_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1023\/A:1008747332633","volume":"14","author":"J. Kennington","year":"1999","unstructured":"Kennington, J., Nair, V., Rahman, M.: Optimization based algorithms for finding minimal cost ring covers in survivable networks. Computational Optimization and Applications\u00a014(2), 219\u2013230 (1999)","journal-title":"Computational Optimization and Applications"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(94)00058-L","volume":"60","author":"F. Lazebnik","year":"1995","unstructured":"Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with arbitrary large girth and of large size. Discrete Applied Mathematics\u00a060, 275\u2013284 (1995)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"53_CR15","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1145\/321958.321974","volume":"23","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: On the complexity of edge traversing. Journal of the ACM\u00a023(3), 544\u2013554 (1976)","journal-title":"Journal of the ACM"},{"key":"53_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1137\/S0895480197331454","volume":"12","author":"B. Rachavachari","year":"1999","unstructured":"Rachavachari, B., Veerasamy, J.: A 3\/2-approximation algorithm for the mixed postman problem. SIAM journal of Disc. Math.\u00a012, 425\u2013433 (1999)","journal-title":"SIAM journal of Disc. Math."},{"doi-asserted-by":"crossref","unstructured":"Slevinsky, J.B., Grover, W.D., MacGregor, M.H.: An algorithm for survivable network design employing multiple self-healing rings. In: GLOBECOM 1993, pp. 1568\u20131573 (1993)","key":"53_CR17","DOI":"10.1109\/GLOCOM.1993.318334"},{"key":"53_CR18","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/S0097539794267255","volume":"26","author":"C. Thomassen","year":"1997","unstructured":"Thomassen, C.: On the complexity of finding a minimum cycle cover of a graph. SIAM journal of computing\u00a026, 675\u20136777 (1997)","journal-title":"SIAM journal of computing"},{"key":"53_CR19","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"53_CR20","volume-title":"Integer flows and cycle cover of graphs","author":"C.Q. Zhang","year":"1997","unstructured":"Zhang, C.Q.: Integer flows and cycle cover of graphs. Marcel Dekker, Inc., New York (1997)"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:29:54Z","timestamp":1605742194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}