{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T15:07:56Z","timestamp":1745334476255},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,8,11]],"date-time":"2009-08-11T00:00:00Z","timestamp":1249948800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00453-009-9349-5","type":"journal-article","created":{"date-parts":[[2009,8,10]],"date-time":"2009-08-10T15:47:11Z","timestamp":1249919231000},"page":"395-400","source":"Crossref","is-referenced-by-count":7,"title":["Approximability of Packing Disjoint Cycles"],"prefix":"10.1007","volume":"60","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,8,11]]},"reference":[{"key":"9349_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proc. of 46th IEEE FOCS, pp. 226\u2013244 (2005)","DOI":"10.1145\/1060590.1060632"},{"key":"9349_CR2","first-page":"276","volume-title":"Proc. of 37th ACM STOC","author":"M. Andrews","year":"2005","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. of 37th ACM STOC, pp. 276\u2013283. ACM Press, New York (2005)"},{"key":"9349_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0963548302005461","volume":"12","author":"P. Balister","year":"2003","unstructured":"Balister, P.: Packing digraphs with directed closed trials. Comb. Probab. Comput. 12, 1\u201315 (2003)","journal-title":"Comb. Probab. Comput."},{"key":"9349_CR4","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0196-6774(03)00052-X","volume":"48","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48, 239\u2013256 (2003)","journal-title":"J. Algorithms"},{"key":"9349_CR5","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S., Shepherd, B.: An $O(\\sqrt{n})$ approximation and integrality gap for disjoint paths and UFP. Theory Comput. 2, 137\u2013146 (2006)","journal-title":"Theory Comput."},{"issue":"4","key":"9349_CR6","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/1082036.1082038","volume":"52","author":"J. Chuzhoy","year":"2005","unstructured":"Chuzhoy, J., Guha, S., Halperin, E., Khanna, S., Kortsarz, G., Krauthgamer, R., Naor, S.: Tight lower bounds for the asymmetric k-center problem. J. ACM 52(4), 538\u2013551 (2005)","journal-title":"J. ACM"},{"key":"9349_CR7","unstructured":"Chuzhoy, J., Khanna, S.: New hardness results for undirected edge disjoint paths. Manuscript (2005)"},{"key":"9349_CR8","first-page":"252","volume-title":"Proc. of 20th ACM STOC","author":"D. Dor","year":"1992","unstructured":"Dor, D., Tarsi, M.: Graph decomposition is NPC\u2014A complete proof of Holyer\u2019s conjecture. In: Proc. of 20th ACM STOC, pp. 252\u2013263. ACM Press, New York (1992)"},{"key":"9349_CR9","series-title":"LNCS","first-page":"304","volume-title":"Proc. of the 18th Int. Symp. on Algorithms and Computation (ISAAC) 2007","author":"Z. Friggstad","year":"2007","unstructured":"Friggstad, Z., Salavatipour, M.R.: Approximability of packing disjoint cycles. In: Proc. of the 18th Int. Symp. on Algorithms and Computation (ISAAC) 2007. LNCS, pp. 304\u2013315. Springer, Berlin (2007)"},{"issue":"3","key":"9349_CR10","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473\u2013496 (2003). Earlier version in STOC\u201999","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9349_CR11","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s00493-007-2169-9","volume":"27","author":"M.M. Halldorsson","year":"2007","unstructured":"Halldorsson, M.M., Kortsarz, G., Radhakrishnan, J., Sivasubramanian, S.: Complete partitions of graphs. Combinatorica 27(5), 519\u2013550 (2007)","journal-title":"Combinatorica"},{"key":"9349_CR12","unstructured":"Kleinberg, J.: Approximation algorithms for disjoint paths problems. PhD. Thesis, MIT, Cambridge, MA, May 1996"},{"issue":"4","key":"9349_CR13","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/1290672.1290685","volume":"3","author":"M. Krivelevich","year":"2007","unstructured":"Krivelevich, M., Nutov, Z., Salavatipour, M.R., Verstraete, J., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Trans. Algorithms 3(4), 48 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9349_CR14","first-page":"191","volume-title":"Proc. of 32nd ACM STOC","author":"A. Samorodnitsky","year":"2000","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proc. of 32nd ACM STOC, pp. 191\u2013199. ACM Press, New York (2000)"},{"key":"9349_CR15","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 281\u2013288 (1995)","journal-title":"Combinatorica"},{"key":"9349_CR16","unstructured":"Varadarajan, K.R., Venkataraman, G.: Graph decomposition and a greedy algorithm for edge-disjoint paths. In: Proc. of 15 ACM-SIAM SODA, pp. 379\u2013380 (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9349-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9349-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9349-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T08:48:12Z","timestamp":1685090892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9349-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,11]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9349"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9349-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,11]]}}}