{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T11:08:10Z","timestamp":1753182490198,"version":"3.37.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319748740"},{"type":"electronic","value":"9783319748757"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-74875-7_2","type":"book-chapter","created":{"date-parts":[[2018,1,27]],"date-time":"2018-01-27T01:42:30Z","timestamp":1517017350000},"page":"11-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Walk in the Clouds: Routing Through VNFs on Bidirected Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4635-4480","authenticated-orcid":false,"given":"Klaus-Tycho","family":"Foerster","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6211-077X","authenticated-orcid":false,"given":"Mahmoud","family":"Parham","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":[[2018,1,28]]},"reference":[{"key":"2_CR1","unstructured":"Amiri, S.A., Foerster, K.-T., Jacob, R., Schmid, S.: Charting the Complexity Landscape of Waypoint Routing. arXiv preprint arXiv:1705.00055 (2017)"},{"key":"2_CR2","unstructured":"Amiri, S.A., Foerster, K.-T., Schmid, S.: Walking through waypoints. arXiv preprint arXiv:1708.09827 (2017)"},{"issue":"2","key":"2_CR3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M.H., Hajiaghayi, M.T., Karloff, H.J.: Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput. 40(2), 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"key":"2_CR4","unstructured":"Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of SODA (1998)"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Lee, K.-W., Nagarajan, V., Zafer, M.: Minimum congestion mapping in a cloud. In: Proceedings of PODC (2011)","DOI":"10.1145\/1993806.1993854"},{"issue":"1","key":"2_CR6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"2_CR7","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":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-662-43948-7_18","volume-title":"Automata, Languages, and Programming","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Shortest two disjoint paths in polynomial time. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 211\u2013222. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_18"},{"issue":"1","key":"2_CR9","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","journal-title":"J. ACM"},{"key":"2_CR10","unstructured":"Chanas, P.: Reseaux ATM: conception et optimisation. Ph.D. thesis, University of Grenoble (1998)"},{"key":"2_CR11","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"2_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"2_CR13","unstructured":"Edmonds, J., Johnson, E.: Matching: a well-solved class of linear programs. In: Combinatorial Structures and their Applications: Proceedings of the Calgary Symposium, pp. 88\u201392. Gordon and Breach, New York (1970)"},{"key":"2_CR14","unstructured":"ETSI: Network functions virtualisation - introductory white paper. White Paper, October 2013"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-319-49259-9_11","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"G Even","year":"2016","unstructured":"Even, G., Medina, M., Patt-Shamir, B.: On-line path computation and function placement in SDNs. In: Bonakdarpour, B., Petit, F. (eds.) SSS 2016. LNCS, vol. 10083, pp. 131\u2013147. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49259-9_11"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-319-48314-6_24","volume-title":"Structural Information and Communication Complexity","author":"G Even","year":"2016","unstructured":"Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in SDNs. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 374\u2013390. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48314-6_24"},{"key":"2_CR17","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."},{"key":"2_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Hartert, R., Vissicchio, S., Schaus, P., Bonaventure, O., Filsfils, C., Telkamp, T., Francois, P.: A declarative and expressive approach to control forwarding paths in carrier-grade networks. In: Proceedings of SIGCOMM (2015)","DOI":"10.1145\/2785956.2787495"},{"issue":"1","key":"2_CR20","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimumspanning trees: Part II. Math. Program. 1(1), 6\u201325 (1971)","journal-title":"Math. Program."},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Sherry, J., et al.: Making middleboxes someone else\u2019s problem: network processing as a cloud service. In: Proceedings of ACM SIGCOMM (2012)","DOI":"10.1145\/2342356.2342359"},{"issue":"1","key":"2_CR22","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.dam.2008.04.024","volume":"157","author":"A Jarry","year":"2009","unstructured":"Jarry, A., P\u00e9rennes, S.: Disjoint paths in symmetric digraphs. Discrete Appl. Math. 157(1), 90\u201397 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"15","key":"2_CR23","doi-asserted-by":"crossref","first-page":"2208","DOI":"10.1016\/j.dam.2012.05.008","volume":"160","author":"A Jarry","year":"2012","unstructured":"Jarry, A.: Multiflows in symmetric digraphs. Discrete Appl. Math. 160(15), 2208\u20132220 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"2_CR24","doi-asserted-by":"crossref","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2_CR25","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.A.: The disjoint paths problem in quadratic time. J. Comb. Theor. Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"3","key":"2_CR26","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":"2_CR27","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":"2_CR28","doi-asserted-by":"crossref","unstructured":"Klein, P.N.: A subset spanner for planar graphs, with application to subset TSP. In: Proceedings of STOC (2006)","DOI":"10.1145\/1132516.1132620"},{"key":"2_CR29","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":"2_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-319-25258-2_8","volume-title":"Structural Information and Communication Complexity","author":"T Lukovszki","year":"2015","unstructured":"Lukovszki, T., Schmid, S.: Online admission control and embedding of service chains. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 104\u2013118. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-25258-2_8"},{"key":"2_CR31","unstructured":"Napper, J., Haeffner, W., Stiemerling, M., Lopez, D.R., Uttaro, J.: Service Function Chaining Use Cases in Mobile Networks. Internet-draft, IETF (2016)"},{"key":"2_CR32","doi-asserted-by":"publisher","unstructured":"Naves, G., Seb\u00f6, A.: Multiflow feasibility: an annotated tableau. In: Cook, W., Lov\u00e1sz, L., Vygen. J. (eds.) Research Trends in Combinatorial Optimization, pp. 261\u2013283. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-76796-1_12","DOI":"10.1007\/978-3-540-76796-1_12"},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Sk\u00f6ldstr\u00f6m, P., et al.: Towards unified programmability of cloud and carrier infrastructure. In: Proceedings of EWSDN (2014)","DOI":"10.1109\/EWSDN.2014.18"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Soul\u00e9, R., et al.: Merlin: a language for provisioning network resources. In: Proceedings of ACM CoNEXT (2014)","DOI":"10.1145\/2674005.2674989"},{"issue":"1","key":"2_CR35","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\u00a0.XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"2_CR36","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph steiner tree approximation. SIAM J. Discrete Math. 19(1), 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"2_CR37","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. (TOCS) 2(4), 277\u2013288 (1984)","journal-title":"ACM Trans. Comput. Syst. (TOCS)"},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"Seb\u00f6, 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":"2_CR39","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1287\/ijoc.8.3.235","volume":"8","author":"R Vachani","year":"1996","unstructured":"Vachani, R., Shulman, A., Kubat, P., Ward, J.: Multicommodity flows in ring networks. INFORMS J. Comput. 8(3), 235\u2013242 (1996)","journal-title":"INFORMS J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects of Cloud Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-74875-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T17:43:55Z","timestamp":1570643035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-74875-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319748740","9783319748757"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-74875-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}