{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:49:41Z","timestamp":1772909381899,"version":"3.50.1"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319200859","type":"print"},{"value":"9783319200866","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-20086-6_22","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T08:27:10Z","timestamp":1434702430000},"page":"286-297","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["On Balanced Separators in Road Networks"],"prefix":"10.1007","author":[{"given":"Aaron","family":"Schild","sequence":"first","affiliation":[]},{"given":"Christian","family":"Sommer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: 39th ACM Symposium on Theory of Computing (STOC), pp. 227\u2013236 (2007)","DOI":"10.1145\/1250790.1250823"},{"key":"22_CR2","unstructured":"Andersen, R., Lang, K.J.: An algorithm for improving graph partitions. In: 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 651\u2013660 (2008)"},{"issue":"1","key":"22_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0095-8956(86)90026-2","volume":"41","author":"T Andreae","year":"1986","unstructured":"Andreae, T.: On a pursuit game played on graphs for which a minor is excluded. Journal of Combinatorial Theory, Series B 41(1), 37\u201347 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"22_CR4","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N Alon","year":"1990","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3(4), 801\u2013808 (1990). Announced at STOC 1990","journal-title":"Journal of the American Mathematical Society"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"TN Bui","year":"1987","unstructured":"Bui, T.N., Chaudhuri, S., Leighton, F.T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica 7(2), 171\u2013191 (1987). Announced at FOCS 1984","journal-title":"Combinatorica"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-39206-1_9","volume-title":"Automata, Languages, and Programming","author":"R Bauer","year":"2013","unstructured":"Bauer, R., Columbus, T., Rutter, I., Wagner, D.: Search-space size in contraction hierarchies. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 93\u2013104. Springer, Heidelberg (2013)"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/3-540-44745-8_24","volume-title":"Energy Minimization Methods in Computer Vision and Pattern Recognition","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut\/max-flow algorithms for energy minimization in vision. In: Figueiredo, M., Zerubia, J., Jain, A.K. (eds.) EMMCVPR 2001. LNCS, vol. 2134, pp. 359\u2013374. Springer, Heidelberg (2001)"},{"key":"22_CR8","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning (2013). arXiv, abs\/1311.3144"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.: Benchmarking for graph clustering and partitioning. In: Encyclopedia of Social Network Analysis and Mining, pp. 73\u201382 (2014)","DOI":"10.1007\/978-1-4614-6170-8_23"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering. In: 10th DIMACS Implementation Challenge Workshop of Contemporary Mathematics, vol. 588 (2013)","DOI":"10.1090\/conm\/588"},{"issue":"11","key":"22_CR11","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"23","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 23(11), 1222\u20131239 (2001). Announced at ICCV 1999","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"2","key":"22_CR12","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Computational Complexity 15(2), 94\u2013114 (2006). Announced at CCC 2005","journal-title":"Computational Complexity"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Delling, D., Fleischman, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.: An exact combinatorial algorithm for minimum graph bisection. Mathematical Programming Series A (2014)","DOI":"10.1007\/s10107-014-0811-z"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: Implementation challenge for shortest paths. In: Encyclopedia of Algorithms (2008)","DOI":"10.1007\/978-0-387-30162-4_181"},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-642-20662-7_32","volume-title":"Experimental Algorithms","author":"D Delling","year":"2011","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Customizable route planning. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 376\u2013387. Springer, Heidelberg (2011)"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Razenshteyn, I., Werneck, R.F.F.: Graph partitioning with natural cuts. In: 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 1135\u20131146 (2011)","DOI":"10.1109\/IPDPS.2011.108"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Delling, D., Holzer, M., M\u00fcller, K., Schulz, F., Wagner, D.: High-performance multi-level routing. In: The Shortest Path Problem: 9th DIMACS Implementation Challenge, vol. 74, pp. 73\u201392 (2009)","DOI":"10.1090\/dimacs\/074\/04"},{"issue":"5","key":"22_CR18","first-page":"1277","volume":"11","author":"EA Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Doklady Akademii Nauk SSSR; Translation in Soviet Mathematics Doklady 11(5), 1277\u20131280 (1970)","journal-title":"Doklady Akademii Nauk SSSR; Translation in Soviet Mathematics Doklady"},{"issue":"4","key":"22_CR19","first-page":"369","volume":"11","author":"HN Djidjev","year":"1985","unstructured":"Djidjev, H.N.: A linear algorithm for partitioning graphs of fixed genus. Serdica. Bulgariacae mathematicae publicationes 11(4), 369\u2013387 (1985)","journal-title":"Serdica. Bulgariacae mathematicae publicationes"},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HN Djidjev","year":"1997","unstructured":"Djidjev, H.N.: Efficient algorithms for shortest path queries in planar digraphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol. 1197, pp. 151\u2013165. Springer, Heidelberg (1997)"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-319-07959-2_23","volume-title":"Experimental Algorithms","author":"J Dibbelt","year":"2014","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271\u2013282. Springer, Heidelberg (2014)"},{"issue":"5","key":"22_CR22","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72(5), 868\u2013889 (2006). Announced at FOCS 2001","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"22_CR23","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16(6), 1004\u20131022 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/978-3-642-23719-5_39","volume-title":"Algorithms \u2013 ESA 2011","author":"AV Goldberg","year":"2011","unstructured":"Goldberg, A.V., Hed, S., Kaplan, H., Tarjan, R.E., Werneck, R.F.: Maximum flows by incremental breadth-first search. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 457\u2013468. Springer, Heidelberg (2011)"},{"issue":"3","key":"22_CR25","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"JR Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. Journal of Algorithms 5(3), 391\u2013407 (1984). Announced as TR82-506 in 1982","journal-title":"Journal of Algorithms"},{"issue":"5","key":"22_CR26","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"AV Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. Journal of the ACM 45(5), 783\u2013797 (1998). Announced at FOCS 1997","journal-title":"Journal of the ACM"},{"issue":"1","key":"22_CR27","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55(1), 3\u201323 (1997). Announced at STOC 1994","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Holzer, M., Schulz, F., Wagner, D.: Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics 13(2008). Announced at ALENEX 2006","DOI":"10.1145\/1412228.1412239"},{"key":"22_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-22006-7_12","volume-title":"Automata, Languages and Programming","author":"K Kawarabayashi","year":"2011","unstructured":"Kawarabayashi, K., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 135\u2013146. Springer, Heidelberg (2011)"},{"key":"22_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-13193-6_8","volume-title":"Experimental Algorithms","author":"T Kieritz","year":"2010","unstructured":"Kieritz, T., Luxen, D., Sanders, P., Vetter, C.: Distributed time-dependent contraction hierarchies. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 83\u201393. Springer, Heidelberg (2010)"},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Mozes, S., Sommer, C.: Structured recursive separator decompositions for planar graphs in linear time. In: 45th ACM Symposium on Theory of Computing (STOC), pp. 505\u2013514 (2013)","DOI":"10.1145\/2488608.2488672"},{"key":"22_CR32","doi-asserted-by":"crossref","unstructured":"Khandekar, R., Rao, S., Vazirani, U.V.: Graph partitioning using single commodity flows. Journal of the ACM 56(4) (2009). Announced at STOC 2006","DOI":"10.1145\/1538902.1538903"},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into \n$$\\ell _1$$\n. In: 46th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"22_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-25960-2_25","volume-title":"Integer Programming and Combinatorial Optimization","author":"K Lang","year":"2004","unstructured":"Lang, K., Rao, S.: A flow-based method for improving the expansion or conductance of graph cuts. In: Bienstock, D., Nemhauser, G. (eds.) IPCO 2004. LNCS, vol. 3064, pp. 325\u2013337. Springer, Heidelberg (2004)"},{"issue":"2","key":"22_CR35","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"22_CR36","doi-asserted-by":"crossref","unstructured":"Madry, A.: Navigating central path with electrical flows: from flows to matchings, and back. In: 54th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 253\u2013262 (2013)","DOI":"10.1109\/FOCS.2013.35"},{"key":"22_CR37","doi-asserted-by":"crossref","unstructured":"Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In: 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 209\u2013222 (2012)","DOI":"10.1137\/1.9781611973099.19"},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"Orecchia, L., Schulman, L.J., Vazirani, U.V., Vishnoi, N.K.: On partitioning graphs via single commodity flows. In: 40th ACM Symposium on Theory of Computing (STOC), pp. 461\u2013470 (2008)","DOI":"10.1145\/1374376.1374442"},{"key":"22_CR39","doi-asserted-by":"crossref","unstructured":"Sherman, J.: Breaking the multicommodity flow barrier for \n$$O(\\sqrt{\\log n})$$\n-approximations to sparsest cut. In: 50th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 363\u2013372 (2009)","DOI":"10.1109\/FOCS.2009.66"},{"key":"22_CR40","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer, C.: Shortest-path queries in static networks. ACM Computing Surveys 46, 45:1\u201345:31 (2014)","journal-title":"ACM Computing Surveys"},{"key":"22_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-642-23719-5_40","volume-title":"Algorithms \u2013 ESA 2011","author":"P Sanders","year":"2011","unstructured":"Sanders, P., Schulz, C.: Engineering multilevel graph partitioning algorithms. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 469\u2013480. Springer, Heidelberg (2011)"},{"key":"22_CR42","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Distributed evolutionary graph partitioning. In: 14th Meeting on Algorithm Engineering & Experiments, (ALENEX), pp. 16\u201329 (2012)","DOI":"10.1137\/1.9781611972924.2"},{"key":"22_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-38527-8_16","volume-title":"Experimental Algorithms","author":"P Sanders","year":"2013","unstructured":"Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Demetrescu, C., Marchetti-Spaccamela, A., Bonifaci, V. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164\u2013175. Springer, Heidelberg (2013)"},{"key":"22_CR44","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S1064827593255135","volume":"18","author":"HD Simon","year":"1997","unstructured":"Simon, H.D., Teng, S.-H.: How good is recursive bisection? SIAM Journal on Scientific Computing 18, 1436\u20131445 (1997)","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"4","key":"22_CR45","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1112\/jlms\/s1-26.4.256","volume":"s1\u201326","author":"P Ungar","year":"1951","unstructured":"Ungar, P.: A theorem on planar graphs. Journal of the London Mathematical Society s1\u201326(4), 256\u2013262 (1951)","journal-title":"Journal of the London Mathematical Society"},{"key":"22_CR46","unstructured":"van Walderveen, F., Zeh, N., Arge, L.: Multiway simple cycle separators and I\/O-efficient algorithms for planar graphs. In: 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 901\u2013918 (2013)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-20086-6_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:38:52Z","timestamp":1676943532000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-20086-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319200859","9783319200866"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-20086-6_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}