{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T21:08:56Z","timestamp":1648588136670},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2006,6,27]],"date-time":"2006-06-27T00:00:00Z","timestamp":1151366400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,9]]},"DOI":"10.1007\/s10878-006-8906-y","type":"journal-article","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:47:37Z","timestamp":1151477257000},"page":"83-96","source":"Crossref","is-referenced-by-count":13,"title":["Finding disjoint paths with related path costs"],"prefix":"10.1007","volume":"12","author":[{"given":"Randeep","family":"Bhatia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murali","family":"Kodialam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. V.","family":"Lakshman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,6,27]]},"reference":[{"key":"8906_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, New Jersey"},{"key":"8906_CR2","doi-asserted-by":"crossref","unstructured":"Andrews M, Zhang L (2005) Hardness of the undirected edge-disjoint paths problem. STOC","DOI":"10.1145\/1060590.1060632"},{"key":"8906_CR3","unstructured":"Chekuri C, Khanna SS (2003) Edge disjoint paths revisited. SODA, 628\u2013637"},{"key":"8906_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri C, Khanna S, Shepherd FB (2004) Edge-Disjoint Paths in Planar Graphs. FOCS, 71\u201380","DOI":"10.1109\/FOCS.2004.27"},{"issue":"4","key":"8906_CR5","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even S, Itai A, Shamir A (1976) On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal of Computing, 5(4):691\u2013703","journal-title":"SIAM Journal of Computing"},{"key":"8906_CR6","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune S, Hopcroft J, Wyllie J (1980) The directed subgraph homemorphism problem. Theoretical Computer Science 10:111\u2013121","journal-title":"Theoretical Computer Science"},{"key":"8906_CR7","first-page":"47","volume-title":"Paths, Flows and VLSI-Layout","author":"A Frank","year":"1990","unstructured":"Frank A (1990) Packing paths, circuits, and cuts\u2014a survey. In Korte B, Lovasz L, Promel HJ, Schrijver A, editors, Paths, Flows and VLSI-Layout Springer Verlag, Berlin, 47\u2013100"},{"issue":"1","key":"8906_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg N, Vazirani V, Yannakakis M (1997) Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica, 18(1):3\u201320","journal-title":"Algorithmica"},{"key":"8906_CR9","unstructured":"Garey MR, Johnson DS (1991) Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman WH and Company"},{"key":"8906_CR10","first-page":"473","volume":"67","author":"V Guruswami","year":"2003","unstructured":"Guruswami V, Khanna S, Rajaraman R, Shepherd B, Yannakakis M (2003) Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. JCSS, 67:473\u2013496","journal-title":"JCSS"},{"key":"8906_CR11","unstructured":"Ho P, Mouftah HT (2001) Issues on Diverse Routing for WDM Mesh Networks with Survivability. Tenth International Conference on Computer Communications and Networks (ICCCN)"},{"key":"8906_CR12","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.3230120306","volume":"12","author":"A Itai","year":"1982","unstructured":"Itai A, Perl Y, Shiloach Y (1982) The complexity of finding maximum disjoint paths with length constraints. Networks, 12:277\u2013286","journal-title":"Networks"},{"issue":"3","key":"8906_CR13","first-page":"317","volume":"1","author":"V Kann","year":"1994","unstructured":"Kann V (1994) Polynomially Bounded Minimization Problems That Are Hard to Approximate. Nordic Journal of Computing, 1(3):317\u2013331","journal-title":"Nordic Journal of Computing"},{"key":"8906_CR14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"M Karp R","year":"1975","unstructured":"Karp R M (1975) On the computational complexity of combinatorial problems. Networks, 5:45\u201368","journal-title":"Networks"},{"key":"8906_CR15","unstructured":"Kleinberg J (1996) Approximation Algorithms for Disjoint Paths Problems. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology"},{"key":"8906_CR16","doi-asserted-by":"crossref","unstructured":"Kodialam M, Lakshman TV (2003) Dynamic Routing of Locally Restorable Bandwidth Guaranteed Tunnels using Aggregated Link Usage Information. IEEE\/ACM Trans. Networking 11(3):399\u2013410","DOI":"10.1109\/TNET.2003.813044"},{"key":"8906_CR17","unstructured":"Kolliopoulos SG, Stein C (1998) Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs. IPCO, 153\u2013168"},{"key":"8906_CR18","unstructured":"Laborczi P, Tapolcai J, Ho P, Cinkler T, Recski A, Mouftah HT (2001) Solving asymmetrically weighted optimal or near-optimal disjoint path-pair for the survivable optical networks. Third International Workshop on Design of Reliable Communication Networks (DRCN)"},{"key":"8906_CR19","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1002\/net.3230220705","volume":"22","author":"CL Li","year":"1992","unstructured":"Li CL, McCormick ST, Simchi-Levi D (1992) Finding disjoint paths with different path costs: Complexity and algorithms. Networks, 22:653\u2013667","journal-title":"Networks"},{"key":"8906_CR20","doi-asserted-by":"crossref","unstructured":"Li CL, McCormick ST, Simchi-Levi D (1990) The complexity of finding two disjoint paths with min-max objective function. Discrete Applied Math, 26(1)","DOI":"10.1016\/0166-218X(90)90024-7"},{"key":"8906_CR21","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"8906_CR22","doi-asserted-by":"crossref","unstructured":"Plotkin S (1995) Competitive Routing of Virtual Circuits in ATM Networks. IEEE Journal on selected areas in communications, 13(6)","DOI":"10.1109\/49.400667"},{"key":"8906_CR23","volume-title":"Paths, Flows and VLSI-Layout","author":"N Robertson","year":"1990","unstructured":"Robertson N, Seymour PD (1990) Outline of a disjoint paths algorithm. In Korte B, Lovasz L, Promel HJ, Schrijver A, editors, Paths, Flows and VLSI-Layout. Springer Verlag, Berlin"},{"key":"8906_CR24","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1002\/net.3230140405","volume":"14","author":"D Ronen","year":"1984","unstructured":"Ronen D, Perl Y (1984) Heuristics for finding a maximum number of disjoint bounded paths. Networks, 14:531\u2013544","journal-title":"Networks"},{"key":"8906_CR25","doi-asserted-by":"crossref","unstructured":"Shiloach Y (1980) A polynomial solution to the undirected two path problem. Journal of the ACM, 27(3):445\u2013456","DOI":"10.1145\/322203.322207"},{"key":"8906_CR26","doi-asserted-by":"crossref","unstructured":"Srinivasan A (1997) Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. FOCS, 416\u2013425","DOI":"10.1109\/SFCS.1997.646130"},{"key":"8906_CR27","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/net.3230040204","volume":"4","author":"JW Suurballe","year":"1974","unstructured":"Suurballe JW (1974) Disjoint paths in a network. Networks, 4:125\u2013145","journal-title":"Networks"},{"key":"8906_CR28","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"JW Suurballe","year":"1984","unstructured":"Suurballe JW, Tarjan RE (1984) A quick method for finding shortest pair of disjoint paths. Networks, 14:325\u2013336.","journal-title":"Networks"},{"key":"8906_CR29","unstructured":"Varadarajan KR, Venkataraman G (2004) Graph decomposition and a greedy algorithm for edge-disjoint paths. SODA, 379\u2013380"},{"key":"8906_CR30","doi-asserted-by":"crossref","DOI":"10.1109\/INFCOM.2004.1354541","volume-title":"On Finding Disjoint Paths in Single and Dual Link Cost Networks","author":"D Xu","year":"2004","unstructured":"Xu D, Chen Y, Xiong Y, Qiao C, He X (2004) On Finding Disjoint Paths in Single and Dual Link Cost Networks. IEEE INFOCOM, Hong Kong"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-8906-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-8906-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-8906-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:10Z","timestamp":1559261890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-8906-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6,27]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["8906"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-8906-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6,27]]}}}