{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:55:42Z","timestamp":1725569742853},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_3","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"3-14","source":"Crossref","is-referenced-by-count":8,"title":["Complexity Results for the Spanning Tree Congestion Problem"],"prefix":"10.1007","author":[{"given":"Yota","family":"Otachi","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT, ECCC TR03-049 (2003)"},{"key":"3_CR2","doi-asserted-by":"publisher","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.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR4","doi-asserted-by":"publisher","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. Theoret. Comput. Sci.\u00a0310, 329\u2013354 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR5","doi-asserted-by":"publisher","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\u00a047, 27\u201351 (2007)","journal-title":"Algorithmica"},{"key":"3_CR6","doi-asserted-by":"publisher","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.\u00a08, 359\u2013387 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"3_CR7","doi-asserted-by":"publisher","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\u00a029, 511\u2013519 (2009)","journal-title":"Discuss. Math. Graph Theory"},{"key":"3_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"3_CR9","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.\u00a026, 257\u2013286 (1992)","journal-title":"Theor. Inform. Appl."},{"key":"3_CR10","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-540-70575-8_49","volume-title":"Automata, Languages and Programming","author":"F.F. Dragan","year":"2008","unstructured":"Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 597\u2013608. Springer, Heidelberg (2008)"},{"key":"3_CR12","doi-asserted-by":"publisher","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.\u00a0108, 85\u2013103 (2001)","journal-title":"Discrete Appl. Math."},{"key":"3_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. J. Comput.\u00a051, 326\u2013362 (2008)","journal-title":"J. Comput."},{"key":"3_CR15","doi-asserted-by":"publisher","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\u00a021, 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"3_CR16","doi-asserted-by":"publisher","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.\u00a0308, 1801\u20131809 (2008)","journal-title":"Discrete Math."},{"key":"3_CR17","doi-asserted-by":"publisher","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.\u00a0309, 4215\u20134224 (2009)","journal-title":"Discrete Math."},{"key":"3_CR18","doi-asserted-by":"publisher","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.\u00a0309, 6644\u20136648 (2009)","journal-title":"Discrete Math."},{"key":"3_CR19","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976)"},{"key":"3_CR20","doi-asserted-by":"publisher","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.\u00a0309, 4653\u20134655 (2009)","journal-title":"Discrete Math."},{"key":"3_CR21","doi-asserted-by":"publisher","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.\u00a0285, 219\u2013226 (2004)","journal-title":"Discrete Math."},{"key":"3_CR22","doi-asserted-by":"publisher","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.\u00a0310, 1204\u20131209 (2010)","journal-title":"Discrete Math."},{"key":"3_CR23","unstructured":"Raspaud, A., S\u00fdkora, O., Vr\u0165o, I.: Congestion and dilation, similarities and differences: A survey. In: SIROCCO 2000, pp. 269\u2013280. Carleton Scientific (2000)"},{"key":"3_CR24","doi-asserted-by":"publisher","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. Combin. Theory Ser. B\u00a052, 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"3_CR25","doi-asserted-by":"publisher","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\u00a020, 235\u2013252 (1987)","journal-title":"Math. Syst. Theory"}],"container-title":["Lecture Notes in Computer Science","Graph Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16926-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T00:49:21Z","timestamp":1553215761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}