{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:45:45Z","timestamp":1760240745036,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T00:00:00Z","timestamp":1568678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA654\/19-2","WA654\/22-2"],"award-info":[{"award-number":["WA654\/19-2","WA654\/22-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009133","name":"Karlsruher Institut f\u00fcr Technologie","doi-asserted-by":"publisher","award":["KIT-Publication Fund"],"award-info":[{"award-number":["KIT-Publication Fund"]}],"id":[{"id":"10.13039\/100009133","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present a mapping between rooted tree decompositions and node separator based multilevel graph partitions. Significant research into both tree decompositions and graph partitions exists. We hope that our result allows for an easier knowledge transfer between the two research avenues.<\/jats:p>","DOI":"10.3390\/a12090198","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T04:50:21Z","timestamp":1569214221000},"page":"198","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Correspondence between Multilevel Graph Partitions and Tree Decompositions"],"prefix":"10.3390","volume":"12","author":[{"given":"Michael","family":"Hamann","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben","family":"Strasser","sequence":"additional","affiliation":[{"name":"Independent Researcher, 71149 Bondorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., and Wagner, D. (2013). Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge, American Mathematical Society.","DOI":"10.1090\/conm\/588"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","article-title":"Recent Advances in Graph Partitioning","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Stanton, I., and Kliot, G. (2012, January 12\u201316). Streaming Graph Partitioning for Large Distributed Graphs. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China.","DOI":"10.1145\/2339530.2339722"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Gkantsidis, C., Radunovic, B., and Vojnovic, M. (2014, January 24\u201328). FENNEL: Streaming graph partitioning for massive scale graphs. Proceedings of the 7th ACM International Conference on Web Search and Data Mining, New York, NY, USA.","DOI":"10.1145\/2556195.2556213"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Martella, C., Logothetis, D., Loukas, A., and Siganos, G. (2018, January 16\u201319). Spinner: Scalable Graph Partitioning in the Cloud. Proceedings of the 33rd International Conference on Data Engineering, Paris, France.","DOI":"10.1109\/ICDE.2017.153"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1418","DOI":"10.14778\/3137628.3137650","article-title":"Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner","volume":"10","author":"Kabiljo","year":"2017","journal-title":"Proc. Vldb Endow."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Akhremtsev, Y., Sanders, P., and Schulz, C. (2018, January 27\u201331). High-Quality Shared-Memory Graph Partitioning. Proceedings of the 24th International Conference on Parallel Processing (Euro-Par 2018), Turin, Italy.","DOI":"10.1007\/978-3-319-96983-1_47"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Aydin, K., Bateni, M.H., and Mirrokni, V. (2019). Distributed Balanced Partitioning via Linear Embedding. Algorithms, 12.","DOI":"10.3390\/a12080162"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4613-8369-7_1","article-title":"An Introduction to Chordal Graphs and Clique Trees","volume":"Volume 56","author":"Blair","year":"1993","journal-title":"Graph Theory and Sparse Matrix Computation"},{"key":"ref_10","first-page":"1","article-title":"A Tourist Guide through Treewidth","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybern."},{"key":"ref_11","unstructured":"Bodlaender, H.L. (2007, January 5\u20138). Treewidth: Structure and Algorithms. Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity, Castiglioncello, Italy."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","volume":"20","author":"Karypis","year":"1999","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1.2:1","DOI":"10.1145\/3173045","article-title":"Graph Bisection with Pareto Optimization","volume":"23","author":"Hamann","year":"2018","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1.5:1","DOI":"10.1145\/2886843","article-title":"Customizable Contraction Hierarchies","volume":"21","author":"Dibbelt","year":"2016","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., and van Leeuwen, J. (2000, January 17\u201319). \u03bb-coloring of graphs. Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science, Lille, France.","DOI":"10.1007\/3-540-46541-3_33"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/trsc.1110.0401","article-title":"Exact Routing in Large Road Networks Using Contraction Hierarchies","volume":"46","author":"Geisberger","year":"2012","journal-title":"Transp. Sci."},{"key":"ref_17","unstructured":"(2019, May 11). OpenStreetMap. Available online: https:\/\/www.openstreetmap.org."},{"key":"ref_18","unstructured":"(2019, May 11). GeoFabrik. Available online: https:\/\/download.geofabrik.de\/."},{"key":"ref_19","unstructured":"(2019, May 11). RoutingKit. Available online: https:\/\/github.com\/RoutingKit\/RoutingKit."},{"key":"ref_20","unstructured":"Strasser, B. (2017). Computing Tree Decompositions with FlowCutter: PACE 2017 Submission. arXiv."},{"key":"ref_21","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., and Weller, M. (2017, January 6\u20138). The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. Proceedings of the 12th International Symposium on Parameterized and Exact Computation, Vienna, Austria."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/198\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:21:05Z","timestamp":1760188865000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,17]]},"references-count":21,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090198"],"URL":"https:\/\/doi.org\/10.3390\/a12090198","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,9,17]]}}}