{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T14:24:08Z","timestamp":1772807048164,"version":"3.50.1"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T00:00:00Z","timestamp":1579478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Unions Horizon 2020 research and innovation programme","award":["648527"],"award-info":[{"award-number":["648527"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We initiate the study of a fundamental combinatorial problem: Given a capacitated graph\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>G<\/mml:mi><mml:mo>=<\/mml:mo><mml:mo>(<\/mml:mo><mml:mi>V<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>E<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, find a shortest walk (\u201croute\u201d) from a source\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$${s\\in V}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>s<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> to a destination\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$t\\in V$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> that includes all vertices specified by a set\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$WP \\subseteq V$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>W<\/mml:mi><mml:mi>P<\/mml:mi><mml:mo>\u2286<\/mml:mo><mml:mi>V<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>: the <jats:italic>waypoints<\/jats:italic>. This W<jats:sc>aypoint<\/jats:sc> R<jats:sc>outing<\/jats:sc> P<jats:sc>roblem<\/jats:sc> finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.<\/jats:p>","DOI":"10.1007\/s00453-020-00672-z","type":"journal-article","created":{"date-parts":[[2020,1,20]],"date-time":"2020-01-20T11:03:09Z","timestamp":1579518189000},"page":"1784-1812","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Walking Through Waypoints"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7402-2662","authenticated-orcid":false,"given":"Saeed","family":"Akhoondian Amiri","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4635-4480","authenticated-orcid":false,"given":"Klaus-Tycho","family":"Foerster","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,20]]},"reference":[{"key":"672_CR1","doi-asserted-by":"crossref","unstructured":"Akhoondian\u00a0Amiri, S., Foerster, K.T., Jacob, R., Parham, M., Schmid, S.: Waypoint routing in special networks. In: Proceedings of IFIP Networking Conference (2018)","DOI":"10.23919\/IFIPNetworking.2018.8696560"},{"issue":"1","key":"672_CR2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/3211852.3211859","volume":"48","author":"S Akhoondian Amiri","year":"2018","unstructured":"Akhoondian Amiri, S., Foerster, K.T., Jacob, R., Schmid, S.: Charting the algorithmic complexity of waypoint routing. ACM SIGCOMM Comput. Commun. Rev. 48(1), 42\u201348 (2018)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"672_CR3","doi-asserted-by":"crossref","unstructured":"Akhoondian\u00a0Amiri, S., Foerster, K.T., Schmid, S.: Walking through waypoints. In: Proceedings of LATIN, Lecture Notes in Computer Science, vol. 10807, pp. 37\u201351. Springer (2018)","DOI":"10.1007\/978-3-319-77404-6_4"},{"key":"672_CR4","doi-asserted-by":"crossref","unstructured":"Akhoondian\u00a0Amiri, S., Golshani, A., Kreutzer, S., Siebertz, S.: Vertex disjoint paths in upward planar graphs. In: Proceedings of CSR (2014)","DOI":"10.1007\/978-3-319-06686-8_5"},{"issue":"2","key":"672_CR5","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the hamiltonian cycle problem for bipartite graphs. J. Inf. Process. Lett. 3(2), 73\u201376 (1980)","journal-title":"J. Inf. Process. Lett."},{"issue":"6\u20137","key":"672_CR6","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1016\/j.comgeo.2008.11.004","volume":"42","author":"EM Arkin","year":"2009","unstructured":"Arkin, E.M., Fekete, S.P., Islam, K., Meijer, H., Mitchell, J.S.B., Rodr\u00edguez, Y.N., Polishchuk, V., Rappaport, D., Xiao, H.: Not being (super)thin or solid is hard: a study of grid hamiltonicity. Comput. Geom. 42(6\u20137), 582\u2013605 (2009)","journal-title":"Comput. Geom."},{"issue":"1","key":"672_CR7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"672_CR8","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeld, T., Taslaman, N.: Shortest cycle through specified elements. In: Proceedings of SODA (2012)","DOI":"10.1137\/1.9781611973099.139"},{"key":"672_CR9","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Shortest two disjoint paths in polynomial time. In: Proceedings of ICALP (2014)","DOI":"10.1007\/978-3-662-43948-7_18"},{"key":"672_CR10","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.: Dynamic programming on graphs with bounded treewidth. In: Proceedings of ICALP (1988)","DOI":"10.1007\/3-540-19488-6_110"},{"issue":"1\u20132","key":"672_CR11","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"6","key":"672_CR12","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"672_CR13","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"672_CR14","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An approximation algorithm for treewidth. In: Proceedings of FOCS (2013)","DOI":"10.1109\/FOCS.2013.60"},{"issue":"2","key":"672_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00453-012-9662-2","volume":"68","author":"G Borradaile","year":"2014","unstructured":"Borradaile, G., Demaine, E.D., Tazari, S.: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica 68(2), 287\u2013311 (2014)","journal-title":"Algorithmica"},{"key":"672_CR16","doi-asserted-by":"crossref","unstructured":"Buro, M.: Simple amazons endgames and their connection to hamilton circuits in cubic subgrid graphs. In: Proceedings of Computers and Games (2000)","DOI":"10.1007\/3-540-45579-5_17"},{"issue":"3","key":"672_CR17","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/s00453-007-9129-z","volume":"54","author":"C Chekuri","year":"2009","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: A note on multiflows and treewidth. Algorithmica 54(3), 400\u2013412 (2009)","journal-title":"Algorithmica"},{"key":"672_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"672_CR19","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: Proceedings of FOCS (2013)","DOI":"10.1145\/2591796.2591852"},{"key":"672_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"2","key":"672_CR21","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T Eilam-Tzoreff","year":"1998","unstructured":"Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discrete Appl. Math. 85(2), 113\u2013138 (1998)","journal-title":"Discrete Appl. Math."},{"key":"672_CR22","unstructured":"Ene, A., Mnich, M., Pilipczuk, M., Risteski, A.: On routing disjoint paths in bounded treewidth graphs. In: Proceedings of SWAT (2016)"},{"key":"672_CR23","unstructured":"ETSI: Network functions virtualisation. White Paper (2013)"},{"key":"672_CR24","unstructured":"ETSI: Network functions virtualisation (nfv); use cases. http:\/\/www.etsi.org\/deliver\/etsi_gs\/NFV\/001_099\/001\/01.01.01_60\/gs_NFV001v010101p.pdf (2014). Accessed 7 Jan 2020"},{"key":"672_CR25","doi-asserted-by":"crossref","unstructured":"Even, G., Medina, M., Patt-Shamir, B.: Online path computation and function placement in SDNs. In: Proceedings of SSS (2016)","DOI":"10.1007\/978-3-319-49259-9_11"},{"key":"672_CR26","doi-asserted-by":"crossref","unstructured":"Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in SDNs. In: Proceedings of SIROCCO (2016)","DOI":"10.1007\/978-3-319-48314-6_24"},{"key":"672_CR27","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2559899.2560327","volume":"11","author":"N Feamster","year":"2013","unstructured":"Feamster, N., Rexford, J., Zegura, E.: The road to SDN. Queue 11, 12 (2013)","journal-title":"Queue"},{"key":"672_CR28","unstructured":"Fellows, M., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. In: Proceedings of COCOA. Springer (2007)"},{"issue":"1","key":"672_CR29","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/s00224-014-9569-1","volume":"58","author":"T Fenner","year":"2016","unstructured":"Fenner, T., Lachish, O., Popa, A.: Min-sum 2-paths problems. Theory Comput. Syst. 58(1), 94\u2013110 (2016)","journal-title":"Theory Comput. Syst."},{"key":"672_CR30","doi-asserted-by":"crossref","unstructured":"Fleischner, H.: Eulerian Graphs and Related Topics. Part 1, Volume 2, chap. Chapter X: Algorithms for Eulerian Trails and Cycle Decompositions, Maze Search Algorithms, pp. X.1 \u2013 X.34. North-Holland (1991)","DOI":"10.1016\/S0167-5060(08)70158-4"},{"issue":"1","key":"672_CR31","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0020-0190(92)90128-I","volume":"42","author":"H Fleischner","year":"1992","unstructured":"Fleischner, H., Woeginger, G.J.: Detecting cycles through three fixed vertices in a graph. Inf. Process. Lett. 42(1), 29\u201333 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"672_CR32","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s10107-017-1199-3","volume":"171","author":"K Fleszar","year":"2018","unstructured":"Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. Math. Program. 171(1), 433\u2013461 (2018)","journal-title":"Math. Program."},{"key":"672_CR33","doi-asserted-by":"crossref","unstructured":"Foerster, K.T., Parham, M., Schmid, S.: A walk in the clouds: Routing through vnfs on bidirected networks. In: Proceedings of ALGOCLOUD (2017)","DOI":"10.1007\/978-3-319-74875-7_2"},{"key":"672_CR34","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.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"672_CR35","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.: The complexity of finding maximum disjoint paths with length constraints. Networks 12(3), 277\u2013286 (1982)","journal-title":"Networks"},{"issue":"1","key":"672_CR36","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"key":"672_CR37","unstructured":"Kawarabayashi, K.: An improved algorithm for finding cycles through elements. In: Proceedings of IPCO (2008)"},{"issue":"3","key":"672_CR38","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0221032","volume":"21","author":"S Khuller","year":"1992","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: Processor efficient parallel algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph. SIAM J. Comput. 21(3), 486\u2013506 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"672_CR39","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1137\/0220022","volume":"20","author":"S Khuller","year":"1991","unstructured":"Khuller, S., Schieber, B.: Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs. SIAM J. Comput. 20(2), 352\u2013375 (1991)","journal-title":"SIAM J. Comput."},{"key":"672_CR40","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Marx, D.: A subexponential parameterized algorithm for subset TSP on planar graphs. In: Proceedings of SODA (2014)","DOI":"10.1137\/1.9781611973402.131"},{"key":"672_CR41","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"9","key":"672_CR42","doi-asserted-by":"crossref","first-page":"1765","DOI":"10.1109\/JSAC.2011.111002","volume":"29","author":"S Knight","year":"2011","unstructured":"Knight, S., Nguyen, H.X., Falkner, N., Bowden, R.A., Roughan, M.: The internet topology zoo. IEEE J. Sel. Areas Commun. 29(9), 1765\u20131775 (2011)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"672_CR43","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Sommer, C.: On shortest disjoint paths in planar graphs. In: Proceedings of ISAAC (2009)","DOI":"10.1007\/978-3-642-10631-6_31"},{"key":"672_CR44","volume-title":"Paths, Flows, and VLSI-Layout","author":"B Korte","year":"1990","unstructured":"Korte, B., Lovasz, L., Pr\u00f6mel, H.J., Schrijver, L.: Paths, Flows, and VLSI-Layout. Springer, Berlin (1990)"},{"issue":"1","key":"672_CR45","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2875951.2875956","volume":"46","author":"T Lukovszki","year":"2016","unstructured":"Lukovszki, T., Rost, M., Schmid, S.: It\u2019s a match! near-optimal and incremental middlebox deployment. ACM SIGCOMM Comput. Commun. Rev. 46(1), 30\u201336 (2016)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"672_CR46","doi-asserted-by":"crossref","unstructured":"Lukovszki, T., Rost, M., Schmid, S.: Approximate and incremental network function placement. In: Journal of Parallel and Distributed Computing (JPDC) (2018)","DOI":"10.1016\/j.jpdc.2018.06.006"},{"key":"672_CR47","doi-asserted-by":"crossref","unstructured":"Lukovszki, T., Schmid, S.: Online admission control and embedding of service chains. In: SIROCCO (2015)","DOI":"10.1007\/978-3-319-25258-2_8"},{"issue":"2","key":"672_CR48","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.ipl.2003.09.016","volume":"89","author":"D Marx","year":"2004","unstructured":"Marx, D.: List edge multicoloring in graphs with few cycles. Inf. Process. Lett. 89(2), 85\u201390 (2004)","journal-title":"Inf. Process. Lett."},{"key":"672_CR49","first-page":"261","volume-title":"Research Trends in Combinatorial Optimization","author":"G Naves","year":"2008","unstructured":"Naves, G., Seb\u0151, A.: Multiflow feasibility: an annotated tableau. In: Cook, W.J., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 261\u2013283. Springer, Berlin (2008)"},{"key":"672_CR50","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Appl. Math. 115, 177\u2013186 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"672_CR51","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1109\/18.212275","volume":"39","author":"RG Ogier","year":"1993","unstructured":"Ogier, R.G., Rutenburg, V., Shacham, N.: Distributed algorithms for computing shortest pairs of disjoint paths. IEEE Trans. Inf. Theory 39(2), 443\u2013455 (1993)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"672_CR52","doi-asserted-by":"crossref","unstructured":"Ohtsuki, T.: The two disjoint path problem and wire routing design. In: Graph Theory and Algorithms, pp. 207\u2013216. Springer (1981)","DOI":"10.1007\/3-540-10704-5_18"},{"issue":"2","key":"672_CR53","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems related to the traveling salesman problem. J. Algorithms 5(2), 231\u2013246 (1984)","journal-title":"J. Algorithms"},{"issue":"3","key":"672_CR54","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1142\/S0129054100000247","volume":"11","author":"L Perkovi\u0107","year":"2000","unstructured":"Perkovi\u0107, L., Reed, B.A.: An improved algorithm for finding tree decompositions of small width. Int. J. Found. Comput. Sci. 11(3), 365\u2013371 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"672_CR55","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors.XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"672_CR56","unstructured":"Rost, M.: Topologyzoo treewidth analysis. https:\/\/github.com\/MatthiasRost\/topologyzoo-treewidth-analysis (2019). Accessed 7 Jan 2020"},{"issue":"1","key":"672_CR57","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/3314212.3314214","volume":"49","author":"M Rost","year":"2019","unstructured":"Rost, M., D\u00f6hne, E., Schmid, S.: Parametrized complexity of virtual network embeddings: dynamic and linear programming approximations. ACM SIGCOMM Comput. Commun. Rev. 49(1), 3\u201310 (2019)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"672_CR58","unstructured":"Rost, M., Schmid, S.: Service chain and virtual network embeddings: approximations using randomized rounding. arXiv preprint 1604.02180 (2016)"},{"key":"672_CR59","doi-asserted-by":"crossref","unstructured":"Rost, M., Schmid, S.: Virtual network embedding approximations: Leveraging randomized rounding. In: Proceedings of IEEE\/ACM Transactions on Networking (ToN) (2019)","DOI":"10.23919\/IFIPNetworking.2018.8696623"},{"issue":"4","key":"672_CR60","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/357401.357402","volume":"2","author":"JH Saltzer","year":"1984","unstructured":"Saltzer, J.H., Reed, D.P., Clark, D.D.: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4), 277\u2013288 (1984)","journal-title":"ACM Trans. Comput. Syst."},{"key":"672_CR61","volume-title":"A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-Width","author":"P Scheffler","year":"1994","unstructured":"Scheffler, P.: A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-Width. Technical Report, TU Berlin (1994)"},{"issue":"4","key":"672_CR62","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Comput. 23(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"key":"672_CR63","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., van Zuylen, A.: The salesman\u2019s improved paths: A 3\/2+1\/34 approximation. In: Proceedings of FOCS (2016)","DOI":"10.1109\/FOCS.2016.21"},{"issue":"3","key":"672_CR64","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"PD Seymour","year":"1980","unstructured":"Seymour, P.D.: Disjoint paths in graphs. Discrete Math. 29(3), 293\u2013309 (1980)","journal-title":"Discrete Math."},{"issue":"3","key":"672_CR65","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y Shiloach","year":"1980","unstructured":"Shiloach, Y.: A polynomial solution to the undirected two paths problem. J. ACM 27(3), 445\u2013456 (1980)","journal-title":"J. ACM"},{"issue":"1","key":"672_CR66","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y Shiloach","year":"1978","unstructured":"Shiloach, Y., Perl, Y.: Finding two disjoint paths between two pairs of vertices in a graph. J. ACM 25(1), 1\u20139 (1978)","journal-title":"J. ACM"},{"issue":"4","key":"672_CR67","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s11276-005-1765-0","volume":"11","author":"A Srinivas","year":"2005","unstructured":"Srinivas, A., Modiano, E.: Finding minimum energy disjoint paths in wireless ad-hoc networks. Wirel. Netw. 11(4), 401\u2013417 (2005)","journal-title":"Wirel. Netw."},{"key":"672_CR68","unstructured":"Taslaman, N.: Exponential-time algorithms and complexity of NP-hard graph problems. Ph.D. thesis, IT University of Copenhagen, Denmark (2013)"},{"issue":"4","key":"672_CR69","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"1","author":"C Thomassen","year":"1980","unstructured":"Thomassen, C.: 2-linked graphs. Eur. J. Comb. 1(4), 371\u2013378 (1980)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"672_CR70","first-page":"19","volume":"7","author":"E de Verdi\u00e8re","year":"2011","unstructured":"de Verdi\u00e8re, E., Schrijver, A.: Shortest vertex-disjoint two-face paths in planar graphs. ACM Trans. Algorithms 7(2), 19 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"672_CR71","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s004539910002","volume":"26","author":"X Zhou","year":"2000","unstructured":"Zhou, X., Tamura, S., Nishizeki, T.: Finding edge-disjoint paths in partial k-trees. Algorithmica 26(1), 3\u201330 (2000)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00672-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00672-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00672-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:38:27Z","timestamp":1611016707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00672-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,20]]},"references-count":71,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["672"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00672-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,20]]},"assertion":[{"value":"30 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}