{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:17Z","timestamp":1740122417662,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T00:00:00Z","timestamp":1578960000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T00:00:00Z","timestamp":1578960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00525-z","type":"journal-article","created":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T11:02:49Z","timestamp":1578999769000},"page":"1615-1636","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the approximability of Time Disjoint Walks"],"prefix":"10.1007","volume":"44","author":[{"given":"Alexandre","family":"Bayen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2552-1921","authenticated-orcid":false,"given":"Jesse","family":"Goodman","sequence":"additional","affiliation":[]},{"given":"Eugene","family":"Vinitsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,14]]},"reference":[{"key":"525_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, Berlin"},{"key":"525_CR2","doi-asserted-by":"crossref","unstructured":"Bayen A, Goodman J, Vinitsky E (2018) On the approximability of Time Disjoint Walks. In: Kim D, Uma RN, Zelikovsky A (eds) Proceedings of the 12th international conference on combinatorial optimization and applications (COCOA \u201918), LNCS, vol 11346. Springer, Cham, pp 62\u201378","DOI":"10.1007\/978-3-030-04651-4_5"},{"key":"525_CR3","doi-asserted-by":"crossref","unstructured":"Berman P, Karpinski M (1999) On some tighter inapproximability results. In: Nielsen M, van Emde\u00a0Boas P, Wiedermann J (eds) Proceedings of the 26th international colloquium on automata, languages, and programming (ICALP \u201999), LNCS, vol 1644. Springer, Berlin, pp 200\u2013209","DOI":"10.1007\/3-540-48523-6_17"},{"issue":"9","key":"525_CR4","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45(9):1563\u20131581","journal-title":"Bell Syst Tech J"},{"key":"525_CR5","doi-asserted-by":"crossref","unstructured":"Gro\u00df M, Skutella M (2012) Maximum multicommodity flows over time without intermediate storage. In: Epstein L, Ferragina P (eds) Proceedings of the 20th annual European symposium on algorithms (ESA 2012), LNCS, vol 7501. Springer, Berlin, pp 539\u2013550","DOI":"10.1007\/978-3-642-33090-2_47"},{"issue":"3","key":"525_CR6","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, Khanna S, Rajaraman R, Shepherd B, Yannakakis M (2003) Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J Comput Syst Sci 67(3):473\u2013496","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"525_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5(1):45\u201368","journal-title":"Networks"},{"key":"525_CR8","unstructured":"Kleinberg JM (1996) Approximation algorithms for disjoint paths problems. Ph.D. thesis, Massachusetts Institute of Technology"},{"issue":"4","key":"525_CR9","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.disopt.2010.05.002","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi Y, Sommer C (2010) On shortest disjoint paths in planar graphs. Discrete Optim 7(4):234\u2013245","journal-title":"Discrete Optim"},{"key":"525_CR10","volume-title":"Paths, flows, and VLSI-layout","author":"B Korte","year":"1990","unstructured":"Korte B, Lov\u00e1sz L, Promel HJ, Schrijver A (1990) Paths, flows, and VLSI-layout. Springer, Berlin"},{"key":"525_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T Lengauer","year":"1990","unstructured":"Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Vieweg+Teubner Verlag, Wiesbaden"},{"issue":"4","key":"525_CR12","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D Marx","year":"2005","unstructured":"Marx D (2005) A short proof of the NP-completeness of minimum sum interval coloring. Oper Res Lett 33(4):382\u2013384","journal-title":"Oper Res Lett"},{"issue":"1","key":"525_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson N, Seymour PD (1995) Graph minors. XIII. The disjoint paths problem. J Comb Theory Ser B 63(1):65\u2013110","journal-title":"J Comb Theory Ser B"},{"key":"525_CR14","unstructured":"Scheffler P (1994) A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical report 396, Technische Universit\u00e4t Berlin, Institut f\u00fcr Mathematik"},{"key":"525_CR15","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-540-76796-1_21","volume-title":"Research trends in combinatorial optimization","author":"M Skutella","year":"2009","unstructured":"Skutella M (2009) An introduction to network flows over time. In: Cook W, Lov\u00e1sz L, Vygen J (eds) Research trends in combinatorial optimization. Springer, Berlin, pp 451\u2013482"},{"key":"525_CR16","doi-asserted-by":"crossref","unstructured":"Srinivas A, Modiano E (2003) Minimum energy disjoint path routing in wireless ad-hoc networks. In: Proceedings of the 9th annual international conference on mobile computing and networking (MobiCom \u201903). ACM, pp 122\u2013133","DOI":"10.1145\/938985.938999"},{"issue":"1","key":"525_CR17","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/S0097539796303123","volume":"29","author":"T Szkaliczki","year":"1999","unstructured":"Szkaliczki T (1999) Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete. SIAM J Comput 29(1):274\u2013287","journal-title":"SIAM J Comput"},{"issue":"11","key":"525_CR18","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1109\/26.179933","volume":"40","author":"D Torrieri","year":"1992","unstructured":"Torrieri D (1992) Algorithms for finding an optimal set of short disjoint paths in a communication network. IEEE Trans Commun 40(11):1698\u20131702","journal-title":"IEEE Trans Commun"},{"key":"525_CR19","doi-asserted-by":"crossref","unstructured":"Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the thirty-eighth annual ACM symposium on theory of computing (STOC \u201906). ACM, pp 681\u2013690","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00525-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00525-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00525-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:44:37Z","timestamp":1664354677000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00525-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,14]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["525"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00525-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,1,14]]},"assertion":[{"value":"14 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}