{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:11Z","timestamp":1759638251128},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00453-011-9565-7","type":"journal-article","created":{"date-parts":[[2011,9,9]],"date-time":"2011-09-09T22:33:13Z","timestamp":1315607593000},"page":"85-111","source":"Crossref","is-referenced-by-count":11,"title":["Parameterized Complexity of the Spanning Tree Congestion Problem"],"prefix":"10.1007","volume":"64","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,9,10]]},"reference":[{"key":"9565_CR1","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. 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)","journal-title":"SIAM J. Comput."},{"key":"9565_CR2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"9565_CR3","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0304-3975(03)00424-9","volume":"310","author":"A. Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theor. Comput. Sci. 310, 329\u2013354 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9565_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s00453-006-1209-y","volume":"47","author":"A. Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Le, V.B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47, 27\u201351 (2007)","journal-title":"Algorithmica"},{"key":"9565_CR5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8, 359\u2013387 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9565_CR6","doi-asserted-by":"crossref","first-page":"511","DOI":"10.7151\/dmgt.1461","volume":"29","author":"A. Castej\u00f3n","year":"2009","unstructured":"Castej\u00f3n, A., Ostrovskii, M.I.: Minimum congestion spanning trees of grids and discrete toruses. Discuss. Math., Graph Theory 29, 511\u2013519 (2009)","journal-title":"Discuss. Math., Graph Theory"},{"key":"9565_CR7","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2009","unstructured":"Cormen, T., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9565_CR8","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: Tree-decompositions, minor and complexity issues. Theor. Inform. Appl. 26, 257\u2013286 (1992)","journal-title":"Theor. Inform. Appl."},{"key":"9565_CR9","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"9565_CR10","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52, 866\u2013893 (2005)","journal-title":"J. ACM"},{"issue":"3","key":"9565_CR11","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Math. 18(3), 501\u2013511 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"9565_CR12","first-page":"682","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth,with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682\u2013689. SIAM, Philadelphia (2005)"},{"key":"9565_CR13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00493-008-2140-4","volume":"28","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 19\u201336 (2008)","journal-title":"Combinatorica"},{"key":"9565_CR14","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1109\/SFCS.2005.14","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 637\u2013646. IEEE Computer Society, Los Alamitos (2005)"},{"key":"9565_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-642-02927-1_27","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Approximation algorithms via structural results for apex-minor-free graphs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Lecture Notes in Computer Science, vol. 5555, pp. 316\u2013327. Springer, Berlin (2009)"},{"key":"9565_CR16","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"key":"9565_CR17","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs, Journal of Computer and System Sciences, doi: 10.1016\/j.jcss.2010.10.002","DOI":"10.1016\/j.jcss.2010.10.002"},{"key":"9565_CR18","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1016\/j.tcs.2010.11.034","volume":"412","author":"F.F. Dragan","year":"2011","unstructured":"Dragan, F.F., Fomin, F.V., Golovach, P.A.: Approximation of minimum weight spanners for sparse graphs. Theor. Comput. Sci. 412, 846\u2013852 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9565_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"9565_CR20","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"key":"9565_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"S.P. Fekete","year":"2001","unstructured":"Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Appl. Math. 108, 85\u2013103 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9565_CR22","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.ipl.2010.10.021","volume":"111","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Golovach, P.A., van Leeuwen, E.J.: Spanners of bounded degree graphs. Inf. Process. Lett. 111, 142\u2013144 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9565_CR23","doi-asserted-by":"crossref","first-page":"785","DOI":"10.1016\/j.ejc.2003.07.007","volume":"25","author":"J.F. Geelen","year":"2004","unstructured":"Geelen, J.F., Richter, R.B., Salazar, G.: Embedding grids in surfaces. Eur. J. Comb. 25, 785\u2013792 (2004)","journal-title":"Eur. J. Comb."},{"key":"9565_CR24","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"9565_CR25","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.jctb.2008.06.004","volume":"99","author":"M. Grohe","year":"2009","unstructured":"Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99, 218\u2013228 (2009)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9565_CR26","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"9565_CR27","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1016\/j.disc.2007.04.030","volume":"308","author":"S.W. Hruska","year":"2008","unstructured":"Hruska, S.W.: On tree congestion of graphs. Discrete Math. 308, 1801\u20131809 (2008)","journal-title":"Discrete Math."},{"key":"9565_CR28","doi-asserted-by":"crossref","first-page":"4215","DOI":"10.1016\/j.disc.2008.12.021","volume":"309","author":"K. Kozawa","year":"2009","unstructured":"Kozawa, K., Otachi, Y., Yamazaki, K.: On spanning tree congestion of graphs. Discrete Math. 309, 4215\u20134224 (2009)","journal-title":"Discrete Math."},{"key":"9565_CR29","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9565_CR30","doi-asserted-by":"crossref","first-page":"6644","DOI":"10.1016\/j.disc.2009.07.007","volume":"309","author":"H.-F. Law","year":"2009","unstructured":"Law, H.-F.: Spanning tree congestion of the hypercube. Discrete Math. 309, 6644\u20136648 (2009)","journal-title":"Discrete Math."},{"key":"9565_CR31","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976)"},{"key":"9565_CR32","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"9565_CR33","doi-asserted-by":"crossref","first-page":"4653","DOI":"10.1016\/j.disc.2009.01.012","volume":"309","author":"C. L\u00f6wenstein","year":"2009","unstructured":"L\u00f6wenstein, C., Rautenbach, D., Regen, F.: On spanning tree congestion. Discrete Math. 309, 4653\u20134655 (2009)","journal-title":"Discrete Math."},{"key":"9565_CR34","doi-asserted-by":"crossref","first-page":"22","DOI":"10.4064\/fm-28-1-22-32","volume":"28","author":"S. MacLane","year":"1937","unstructured":"MacLane, S.: A combinatorial condition for planar graphs. Fundam. Math. 28, 22\u201332 (1937)","journal-title":"Fundam. Math."},{"key":"9565_CR35","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.4153\/CJM-1992-076-8","volume":"44","author":"B. Mohar","year":"1992","unstructured":"Mohar, B.: Combinatorial local planarity and the width of graph embeddings. Can. J. Math. 44, 1272\u20131288 (1992)","journal-title":"Can. J. Math."},{"key":"9565_CR36","series-title":"Johns Hopkins Studies in the Mathematical Sciences","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"key":"9565_CR37","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/978-3-642-20877-5_44","volume-title":"Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)","author":"Y. Okamoto","year":"2011","unstructured":"Okamoto, Y., Otachi, Y., Uehara, R., Uno, T.: Hardness results and an exact exponential algorithm for the spanning tree congestion problem. In: Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Lecture Notes in Comput. Sci., vol.\u00a06648, pp.\u00a0452\u2013462 (2011)"},{"key":"9565_CR38","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.disc.2004.02.009","volume":"285","author":"M.I. Ostrovskii","year":"2004","unstructured":"Ostrovskii, M.I.: Minimal congestion trees. Discrete Math. 285, 219\u2013226 (2004)","journal-title":"Discrete Math."},{"key":"9565_CR39","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1016\/j.disc.2009.11.016","volume":"310","author":"M.I. Ostrovskii","year":"2010","unstructured":"Ostrovskii, M.I.: Minimum congestion spanning trees in planar graphs. Discrete Math. 310, 1204\u20131209 (2010)","journal-title":"Discrete Math."},{"key":"9565_CR40","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-642-16926-7_3","volume-title":"Proceedings of the 6th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010)","author":"Y. Otachi","year":"2010","unstructured":"Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.: Complexity results for the spanning tree congestion problem. In: Proceedings of the 6th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Comput. Sci., vol.\u00a06410, pp. 3\u201314 (2010)"},{"key":"9565_CR41","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/3-540-45687-2_5","volume-title":"Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002)","author":"D. Peleg","year":"2002","unstructured":"Peleg, D.: Low stretch spanning trees. In: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Lecture Notes in Comput. Sci., vol.\u00a02420, pp. 68\u201380 (2002)"},{"key":"9565_CR42","first-page":"269","volume-title":"Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2000)","author":"A. Raspaud","year":"2000","unstructured":"Raspaud, A., S\u00fdkora, O., Vr\u0165o, I.: Congestion and dilation, similarities and differences: a survey. In: Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2000), pp. 269\u2013280. Carleton Scientific, Oxford (2000)"},{"key":"9565_CR43","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52, 153\u2013190 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9565_CR44","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89, 43\u201376 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9565_CR45","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory, Ser.\u00a0B 62, 323\u2013348 (1994)","journal-title":"J. Comb. Theory, Ser.\u00a0B"},{"key":"9565_CR46","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01692067","volume":"20","author":"S. Simonson","year":"1987","unstructured":"Simonson, S.: A variation on the min cut linear arrangement problem. Math. Syst. Theory 20, 235\u2013252 (1987)","journal-title":"Math. Syst. Theory"},{"key":"9565_CR47","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jctb.1997.1761","volume":"70","author":"C. Thomassen","year":"1997","unstructured":"Thomassen, C.: A simpler proof of the excluded minor theorem for higher surfaces. J. Comb. Theory, Ser. B 70, 306\u2013311 (1997)","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9565-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T10:10:49Z","timestamp":1686305449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9565-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,10]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9565"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9565-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,10]]}}}