{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:32:18Z","timestamp":1742992338340,"version":"3.40.3"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_1","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:27Z","timestamp":1737497427000},"page":"3-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for\u00a0Treewidth, Pathwidth, and\u00a0Treedepth\u2014A Short Survey"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"key":"1_CR1","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Breese, J.S., Koller, D. (eds.) Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, UAI 2001, pp. 7\u201315. Morgan Kaufmann (2001)"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/S00453-008-9180-4","volume":"56","author":"E Amir","year":"2010","unstructured":"Amir, E.: Approximation algorithms for treewidth. Algorithmica 56, 448\u2013479 (2010). https:\/\/doi.org\/10.1007\/S00453-008-9180-4","journal-title":"Algorithmica"},{"key":"1_CR3","doi-asserted-by":"publisher","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a $$k$$-tree. SIAM J. Algebraic Discrete Methods 8, 277\u2013284 (1987). https:\/\/doi.org\/10.1137\/0608024","DOI":"10.1137\/0608024"},{"key":"1_CR4","doi-asserted-by":"publisher","unstructured":"Bansal, N., Katzelnick, D., Schwartz, R.: Almost logarithmic approximation for cutwidth and pathwidth (2023). https:\/\/doi.org\/10.48550\/ARXIV.2311.15639","DOI":"10.48550\/ARXIV.2311.15639"},{"issue":"2","key":"1_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.7155\/JGAA.00593","volume":"26","author":"M Belbasi","year":"2022","unstructured":"Belbasi, M., F\u00fcrer, M.: An improvement of Reed\u2019s treewidth approximation. J. Graph Algorithms Appl. 26(2), 257\u2013282 (2022). https:\/\/doi.org\/10.7155\/JGAA.00593","journal-title":"J. Graph Algorithms Appl."},{"issue":"6","key":"1_CR6","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1017\/S0963548302005369","volume":"11","author":"P Bellenbaum","year":"2002","unstructured":"Bellenbaum, P., Diestel, R.: Two short proofs concerning tree-decompositions. Comb. Prob. Comput. 11(6), 541\u2013547 (2002). https:\/\/doi.org\/10.1017\/S0963548302005369","journal-title":"Comb. Prob. Comput."},{"key":"1_CR7","volume-title":"Nonserial Dynamic Programming","author":"U Bertele","year":"1972","unstructured":"Bertele, U., Brioschi, F.: Nonserial Dynamic Programming. Academic Press, New York (1972)"},{"key":"1_CR8","doi-asserted-by":"publisher","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, 1305\u20131317 (1996). https:\/\/doi.org\/10.1137\/S0097539793251219","journal-title":"SIAM J. Comput."},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discrete Math. 11, 168\u2013181 (1998). https:\/\/doi.org\/10.1137\/S0895480195282550","DOI":"10.1137\/S0895480195282550"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^k n$$ n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Comput."},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and minimum elimination tree height. J. Algorithms 18, 238\u2013255 (1995). https:\/\/doi.org\/10.1006\/JAGM.1995.1009","DOI":"10.1006\/JAGM.1995.1009"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-55121-2_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, and minimum elimination tree height. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 1\u201312. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55121-2_1"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inform. Comput. 208, 259\u2013275 (2010). https:\/\/doi.org\/10.1016\/J.IC.2009.03.008","DOI":"10.1016\/J.IC.2009.03.008"},{"key":"1_CR15","unstructured":"\u00c9douard Bonnet: Treewidth inapproximability and tight ETH lower bound (2024). https:\/\/arxiv.org\/abs\/2406.11628"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0166-218X(03)00440-2","volume":"136","author":"V Bouchitt\u00e9","year":"2004","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximations. Discret. Appl. Math. 136, 183\u2013196 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(03)00440-2","journal-title":"Discret. Appl. Math."},{"key":"1_CR17","doi-asserted-by":"publisher","unstructured":"Cattell, K., Dinneen, M.J., Fellows, M.R.: A simple linear-time algorithm for finding path-decompositions of small width. Inform. Process. Lett. 57, 197\u2013204 (1996). https:\/\/doi.org\/10.1016\/0020-0190(95)00190-5","DOI":"10.1016\/0020-0190(95)00190-5"},{"issue":"2","key":"1_CR18","doi-asserted-by":"publisher","first-page":"934","DOI":"10.1137\/19M128819X","volume":"35","author":"W Czerwinski","year":"2021","unstructured":"Czerwinski, W., Nadara, W., Pilipczuk, M.: Improved bounds for the excluded-minor approximation of treedepth. SIAM J. Discret. Math. 35(2), 934\u2013947 (2021). https:\/\/doi.org\/10.1137\/19M128819X","journal-title":"SIAM J. Discret. Math."},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9, 302\u2013325 (1983). https:\/\/doi.org\/10.1145\/356044.356047","DOI":"10.1145\/356044.356047"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"28","author":"G Even","year":"1999","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM J. Comput. 28, 2187\u20132214 (1999). https:\/\/doi.org\/10.1137\/S0097539796308217","journal-title":"SIAM J. Comput."},{"key":"1_CR21","volume-title":"Graph Algorithms","author":"S Even","year":"1979","unstructured":"Even, S.: Graph Algorithms. Pitman, London (1979)"},{"key":"1_CR22","doi-asserted-by":"publisher","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th Annual Symposium on Theory of Computing, STOC 2005, pp. 563\u2013572. ACM Press (2005). https:\/\/doi.org\/10.1145\/1060590.1060674","DOI":"10.1145\/1060590.1060674"},{"key":"1_CR23","doi-asserted-by":"publisher","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 629\u2013657 (2008). https:\/\/doi.org\/10.1137\/05064299X","DOI":"10.1137\/05064299X"},{"key":"1_CR24","doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision and the efficiency of polynomial-time algorithms. In: Proceedings of the 21st Annual Symposium on Theory of Computing, STOC 1989, pp. 501\u2013512 (1989). https:\/\/doi.org\/10.1145\/73007.73055","DOI":"10.1145\/73007.73055"},{"key":"1_CR25","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Pilipczuk, M., Wrochna, M.: Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Trans. Algorithms 14(3), 34:1\u201334:45 (2018). https:\/\/doi.org\/10.1145\/3186898","DOI":"10.1145\/3186898"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Groenland, C., Joret, G., Nadara, W., Walczak, B.: Approximating pathwidth for graphs of small treewidth. ACM Trans. Algorithms 19(2), 16:1\u201316:19 (2023). https:\/\/doi.org\/10.1145\/3576044","DOI":"10.1145\/3576044"},{"key":"1_CR27","unstructured":"Kashiwabara, T., Fujisawa, T.: An NP-complete problem on interval graphs. In: Proceedings IEEE Symposium on Circuits and Systems, pp. 82\u201383 (1979)"},{"issue":"4","key":"1_CR28","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.4171\/JEMS\/1133","volume":"24","author":"K Kawarabayashi","year":"2022","unstructured":"Kawarabayashi, K., Rossman, B.: A polynomial excluded-minor approximation of treedepth. J. Eur. Math. Soc. 24(4), 1449\u20131470 (2022). https:\/\/doi.org\/10.4171\/JEMS\/1133","journal-title":"J. Eur. Math. Soc."},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 184\u2013192. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00026","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"1_CR30","doi-asserted-by":"publisher","unstructured":"Korhonen, T., Lokshtanov, D.: An improved parameterized algorithm for treewidth. In: Saha, B., Servedio, R.A. (eds.) Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 528\u2013541. ACM (2023). https:\/\/doi.org\/10.1145\/3564246.3585245","DOI":"10.1145\/3564246.3585245"},{"key":"1_CR31","doi-asserted-by":"publisher","unstructured":"Lagergren, J.: Efficient parallel algorithms for tree-decomposition and related problems. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, pp. 173\u2013182 (1990). https:\/\/doi.org\/10.1109\/FSCS.1990.89536","DOI":"10.1109\/FSCS.1990.89536"},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/JAGM.1996.0002","volume":"20","author":"J Lagergren","year":"1996","unstructured":"Lagergren, J.: Efficient parallel algorithms for graphs of bounded tree-width. J. Algorithms 20, 20\u201344 (1996). https:\/\/doi.org\/10.1006\/JAGM.1996.0002","journal-title":"J. Algorithms"},{"key":"1_CR33","doi-asserted-by":"publisher","unstructured":"Leighton, F.T., Rao, S.: An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximate algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS 1988, pp. 422\u2013431. IEEE (1988). https:\/\/doi.org\/10.1109\/SFCS.1988.21958","DOI":"10.1109\/SFCS.1988.21958"},{"issue":"6","key":"1_CR34","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"FT Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999). https:\/\/doi.org\/10.1145\/331524.331526","journal-title":"J. ACM"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0611010","volume":"11","author":"JWH Liu","year":"1990","unstructured":"Liu, J.W.H.: The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11, 134\u2013172 (1990). https:\/\/doi.org\/10.1137\/0611010","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"1_CR36","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1137\/1034004","volume":"34","author":"JWH Liu","year":"1992","unstructured":"Liu, J.W.H.: The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 34(1), 82\u2013109 (1992). https:\/\/doi.org\/10.1137\/1034004","journal-title":"SIAM Rev."},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(91)90020-Y","volume":"12","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J., Thomas, R.: Algorithms for finding tree-decompositions of graphs. J. Algorithms 12, 1\u201322 (1991). https:\/\/doi.org\/10.1016\/0196-6774(91)90020-Y","journal-title":"J. Algorithms"},{"key":"1_CR38","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. AC, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"1_CR39","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27, 1022\u20131041 (2006). https:\/\/doi.org\/10.1016\/J.EJC.2005.01.010","DOI":"10.1016\/J.EJC.2005.01.010"},{"issue":"6","key":"1_CR40","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1007\/S00373-015-1569-7","volume":"31","author":"J Ne\u0161et\u0159il","year":"2015","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: On low tree-depth decompositions. Graphs Comb. 31(6), 1941\u20131963 (2015). https:\/\/doi.org\/10.1007\/S00373-015-1569-7","journal-title":"Graphs Comb."},{"key":"1_CR41","unstructured":"Pothen, A.: The complexity of optimal elimination trees. Technical Report CS-88-13, Pennsylvania State University (1988). https:\/\/www.cs.purdue.edu\/homes\/apothen\/Papers\/shortest-etree1988.pdf"},{"key":"1_CR42","doi-asserted-by":"publisher","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 755\u2013764. ACM (2010). https:\/\/doi.org\/10.1145\/1806689.1806792","DOI":"10.1145\/1806689.1806792"},{"key":"1_CR43","doi-asserted-by":"publisher","unstructured":"Reed, B.: Finding approximate separators and computing tree-width quickly. In: Proceedings of the 24th Annual Symposium on Theory of Computing, STOC 1992. pp. 221\u2013228. ACM Press, New York (1992). https:\/\/doi.org\/10.1145\/129712.129734","DOI":"10.1145\/129712.129734"},{"key":"1_CR44","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"1_CR45","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63, 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/JCTB.1995.1006","DOI":"10.1006\/JCTB.1995.1006"},{"key":"1_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-030-42071-0_15","volume-title":"Treewidth, Kernels, and Algorithms","author":"H Tamaki","year":"2020","unstructured":"Tamaki, H.: Experimental analysis of treewidth. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms. LNCS, vol. 12160, pp. 214\u2013221. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_15"},{"key":"1_CR47","doi-asserted-by":"publisher","unstructured":"Wu, Y.L., Austrin, P., Pitassi, T., Liu, D.: Inapproximability of treewidth and related problems. J. Artif. Intell. Res. 49, 569\u2013600 (2014). https:\/\/doi.org\/10.1613\/JAIR.4030","DOI":"10.1613\/JAIR.4030"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75409-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:31Z","timestamp":1737497431000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}