{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T03:20:45Z","timestamp":1768274445460,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T00:00:00Z","timestamp":1576108800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T00:00:00Z","timestamp":1576108800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00657-7","type":"journal-article","created":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T15:07:51Z","timestamp":1576163271000},"page":"1574-1600","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Computing Treebreadth"],"prefix":"10.1007","volume":"82","author":[{"given":"Guillaume","family":"Ducoffe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Legay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,12]]},"reference":[{"key":"657_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/net.21631","volume":"67","author":"M Abu-Ata","year":"2016","unstructured":"Abu-Ata, M., Dragan, F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67, 49\u201368 (2016)","journal-title":"Networks"},{"key":"657_CR2","doi-asserted-by":"publisher","first-page":"018702","DOI":"10.1103\/PhysRevLett.94.018702","volume":"94","author":"J Andrade","year":"2005","unstructured":"Andrade, J., Herrmann, H., Andrade, R., da Silva, L.: Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs. Phys. Rev. Lett. 94, 018702 (2005)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"657_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a $$k$$-tree. SIAM J. Algebraic Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"657_CR4","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1137\/16M1057383","volume":"31","author":"R Belmonte","year":"2017","unstructured":"Belmonte, R., Fomin, F.V., Golovach, P.A., Ramanujan, M.S.: Metric dimension of bounded tree-length graphs. SIAM J. Discrete Math. 31(2), 1217\u20131243 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"657_CR5","unstructured":"Berry, A., Pogorelcnik, R., Sigayret, A.: Vertical decomposition of a lattice using clique separators. In: CLA\u201911, Nancy, France, pp. 15\u201329 (2011)"},{"issue":"2","key":"657_CR6","doi-asserted-by":"publisher","first-page":"197","DOI":"10.3390\/a3020197","volume":"3","author":"A Berry","year":"2010","unstructured":"Berry, A., Pogorelcnik, R., Simonet, G.: An introduction to clique minimal separator decomposition. Algorithms 3(2), 197\u2013215 (2010)","journal-title":"Algorithms"},{"issue":"6","key":"657_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender, H.: 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":"657_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.: Treewidth: characterizations, applications, and computations. In: WG 2006, Bergen, Norway, pp. 1\u201314 (2006)","DOI":"10.1007\/11917496_1"},{"key":"657_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fellows, M., Warnow, T.: Two strikes against perfect phylogeny. In: ICALP\u201992, Vienna, Austria, pp. 273\u2013283 (1992)","DOI":"10.1007\/3-540-55719-9_80"},{"issue":"2","key":"657_CR10","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender, H., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"657_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.disc.2005.12.017","volume":"306","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.: Safe separators for treewidth. Discrete Math. 306(3), 337\u2013350 (2006)","journal-title":"Discrete Math."},{"issue":"1","key":"657_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"657_CR13","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F., Chepoi, V., Voloshin, V.: Dually chordal graphs. SIAM J. Discrete Math. 11(3), 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"657_CR14","doi-asserted-by":"crossref","unstructured":"Chechik, S., Larkin, D., Roditty, L., Schoenebeck, G., Tarjan, R., Vassilevska Williams, V.: Better approximation algorithms for the graph diameter. In: ACM SODA\u201914. SIAM, pp. 1041\u20131052 (2014)","DOI":"10.1137\/1.9781611973402.78"},{"key":"657_CR15","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: SCG\u201908, New York, NY, USA, ACM, pp. 59\u201368 (2008)","DOI":"10.1145\/1377676.1377687"},{"issue":"3","key":"657_CR16","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1137\/15M1034039","volume":"30","author":"D Coudert","year":"2016","unstructured":"Coudert, D., Ducoffe, G., Nisse, N.: To approximate treewidth, use treelength!. SIAM J. Discrete Math. 30(3), 1424\u20131436 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"657_CR17","doi-asserted-by":"crossref","unstructured":"de Montgolfier, F., Soto, M., Viennot, L.: Treewidth and hyperbolicity of the internet. In: 2011 10th IEEE International Symposium on Network Computing and Applications (NCA), pp. 25\u201332 (2011)","DOI":"10.1109\/NCA.2011.11"},{"issue":"1","key":"657_CR18","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2007.03.058","volume":"383","author":"Y Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Dragan, F., Gavoille, C., Chenyu, Y.: Spanners for bounded tree-length graphs. Theor. Comput. Sci. 383(1), 34\u201344 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"16","key":"657_CR19","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Math. 307(16), 2008\u20132029 (2007)","journal-title":"Discrete Math."},{"key":"657_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.06.007","volume":"547","author":"F Dragan","year":"2014","unstructured":"Dragan, F., Abu-Ata, M.: Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences. Theoret. Comput. Sci. 547, 1\u201317 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"657_CR21","doi-asserted-by":"publisher","first-page":"884","DOI":"10.1007\/s00453-013-9765-4","volume":"69","author":"F Dragan","year":"2014","unstructured":"Dragan, F., K\u00f6hler, E.: An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs. Algorithmica 69(4), 884\u2013905 (2014)","journal-title":"Algorithmica"},{"key":"657_CR22","doi-asserted-by":"crossref","unstructured":"Dragan, F., K\u00f6hler, E., Leitert, A.: Line-distortion, bandwidth and path-length of a graph. In: Algorithm Theory\u2014SWAT 2014. Springer, pp. 158\u2013169 (2014)","DOI":"10.1007\/978-3-319-08404-6_14"},{"key":"657_CR23","doi-asserted-by":"crossref","unstructured":"Dragan, F., Leitert, A.: On the minimum eccentricity shortest path problem. In: Algorithms and Data Structures\u2014WADS. Springer, pp. 276\u2013288 (2015)","DOI":"10.1007\/978-3-319-21840-3_23"},{"key":"657_CR24","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ipl.2018.01.005","volume":"133","author":"G Ducoffe","year":"2018","unstructured":"Ducoffe, G.: A short note on the complexity of computing strong pathbreadth. Inf. Process. Lett. 133, 56\u201358 (2018)","journal-title":"Inf. Process. Lett."},{"key":"657_CR25","doi-asserted-by":"crossref","unstructured":"Ducoffe, G., Legay, N., Nisse, N.: On the complexity of computing treebreadth. In: IWOCA 2016\u201427th International Workshop on Combinatorial Algorithms, pp. 3\u201315 (2016)","DOI":"10.1007\/978-3-319-44543-4_1"},{"key":"657_CR26","unstructured":"Ducoffe, G., Legay, S., Nisse, N.: On computing tree and path decompositions with metric constraints on the bags. Technical report RR-8842, Inria (2016)"},{"issue":"1","key":"657_CR27","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"657_CR28","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M Golumbic","year":"1994","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Adv. Appl. Math. 15(3), 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"key":"657_CR29","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)"},{"key":"657_CR30","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.: Algorithms on negatively curved spaces. In: FOCS\u201906. IEEE, pp. 119\u2013132 (2006)","DOI":"10.1109\/FOCS.2006.9"},{"key":"657_CR31","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.ipl.2017.07.012","volume":"128","author":"A Leitert","year":"2017","unstructured":"Leitert, A.: 3-Colouring for dually chordal graphs and generalisations. Inf. Process. Lett. 128, 21\u201326 (2017)","journal-title":"Inf. Process. Lett."},{"key":"657_CR32","doi-asserted-by":"crossref","unstructured":"Leitert, A., Dragan, F.: On strong tree-breadth. In: International Conference on Combinatorial Optimization and Applications. Springer, pp. 62\u201376 (2016)","DOI":"10.1007\/978-3-319-48749-6_5"},{"issue":"7","key":"657_CR33","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","volume":"158","author":"D Lokshtanov","year":"2010","unstructured":"Lokshtanov, D.: On the complexity of computing treelength. Discrete Appl. Math. 158(7), 820\u2013827 (2010)","journal-title":"Discrete Appl. Math."},{"key":"657_CR34","doi-asserted-by":"crossref","unstructured":"Mertzios, G., Spirakis, P.: Algorithms and almost tight results for 3-colorability of small diameter graphs. In: International Conference on Current Trends in Theory and Practice of Computer Science. Springer, pp. 332\u2013343 (2013)","DOI":"10.1007\/978-3-642-35843-2_29"},{"issue":"1","key":"657_CR35","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"657_CR36","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1), 171\u2013188 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"657_CR37","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"657_CR38","doi-asserted-by":"crossref","unstructured":"Wang, C., Liu, T., Jiang, W., Xu, K.: Feedback vertex sets on tree convex bipartite graphs. In: COCOA 2012, Banff, AB, Canada, pp. 95\u2013102 (2012)","DOI":"10.1007\/978-3-642-31770-5_9"},{"key":"657_CR39","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1613\/jair.4030","volume":"49","author":"Y Wu","year":"2014","unstructured":"Wu, Y., Austrin, P., Pitassi, T., Liu, D.: Inapproximability of treewidth and related problems. JAIR 49, 569\u2013600 (2014)","journal-title":"JAIR"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00657-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00657-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00657-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T01:14:34Z","timestamp":1607649274000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00657-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,12]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["657"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00657-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,12]]},"assertion":[{"value":"19 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}