{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:43:25Z","timestamp":1725543805091},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540354741"},{"type":"electronic","value":"9783540354758"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11780823_11","type":"book-chapter","created":{"date-parts":[[2006,6,23]],"date-time":"2006-06-23T14:45:59Z","timestamp":1151073959000},"page":"130-142","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Strategies for Routing Edge\u00a0Disjoint Paths in Complete Graphs"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Kosowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. STOC 2005, pp. 276\u2013283 (2005)","DOI":"10.1145\/1060590.1060632"},{"key":"11_CR2","unstructured":"Beauquier, B., Bermond, J.C., Gargano, L., Hell, P., P\u00e8rennes, S., Vaccaro, U.: Graph problems arising from wavelength routing in all-optical networks. In: Proc. WOCS 1997, Geneve, Switzerland (1997)"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bia\u0142ogrodzki, J.: Path Coloring and Routing in Graphs. In: Kubale, M. (ed.) Graph Colorings. Contemporary Math, vol.\u00a0352, pp. 139\u2013152. AMS, USA (2004)","DOI":"10.1090\/conm\/352"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-540-39890-5_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Carmi","year":"2003","unstructured":"Carmi, P., Erlebach, T., Okamoto, Y.: Greedy edge-disjoint paths in complete graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 143\u2013155. Springer, Heidelberg (2003)"},{"key":"11_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-540-27796-5_7","volume-title":"Structural Information and Communication Complexity","author":"S. Choplin","year":"2004","unstructured":"Choplin, S., Narayanan, L., Opatrny, J.: Two-Hop Virtual Path Layout in Tori. In: Kralovic, R., S\u00fdkora, O. (eds.) SIROCCO 2004. LNCS, vol.\u00a03104, pp. 69\u201378. Springer, Heidelberg (2004)"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0304-3975(99)00152-8","volume":"255","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Jansen, K.: The complexity of path coloring and call scheduling. Theoret. Comp. Sci.\u00a0255, 33\u201350 (2001)","journal-title":"Theoret. Comp. Sci."},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1137\/S0895480199361259","volume":"14","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Jansen, K.: The Maximum Edge-Disjoint Paths Problem in Bidirected Trees. SIAM J. Discret. Math.\u00a014, 326\u2013355 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/3-540-44669-9_55","volume-title":"Fundamentals of Computation Theory","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Vukadinovi\u0107, D.: New results for path problems in generalized stars, complete graphs, and brick wall graphs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.\u00a02138, pp. 483\u2013494. Springer, Heidelberg (2001)"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/s00453-002-0992-3","volume":"35","author":"L.M. Favrholdt","year":"2003","unstructured":"Favrholdt, L.M., Nielsen, M.N.: On-line edge-coloring with a fixed number of colors. Algorithmica\u00a035, 176\u2013191 (2003)","journal-title":"Algorithmica"},{"key":"11_CR10","volume-title":"Edge-Colourings of Graphs","author":"S. Fiorini","year":"1977","unstructured":"Fiorini, S., Wilson, R.J.: Edge-Colourings of Graphs. Pittman, USA (1977)"},{"key":"11_CR11","unstructured":"Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proc.\u00a0SODA 1990, pp. 434\u2013443 (1990)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., et al.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci.\u00a067, 473\u2013496 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR13","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proc.\u00a0SODA 2002, pp. 184\u2013193 (2002)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcss.1999.1661","volume":"60","author":"B. Ma","year":"2000","unstructured":"Ma, B., Wang, L.: On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints. J. Comput. Syst. Sci.\u00a060, 1\u201312 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proc.\u00a0FOCS 1997, pp. 416\u2013425 (1997)","DOI":"10.1109\/SFCS.1997.646130"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Canad. J. Math.\u00a06, 347\u2013352 (1954)","journal-title":"Canad. J. Math."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11780823_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:17:07Z","timestamp":1619507827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11780823_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540354741","9783540354758"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11780823_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}