{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:53Z","timestamp":1725582293051},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_44","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T02:35:17Z","timestamp":1303871717000},"page":"452-462","source":"Crossref","is-referenced-by-count":3,"title":["Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem"],"prefix":"10.1007","author":[{"given":"Yoshio","family":"Okamoto","sequence":"first","affiliation":[]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: Fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"44_CR2","unstructured":"Bodlaender, H.L., Kozawa, K., Matsushima, T., Otachi, Y.: Spanning tree congestion of k-outerplanar graphs. In: WAAC 2010, pp. 34\u201339 (2010)"},{"key":"44_CR3","unstructured":"Bodlaender, H.L., Fomin, F.V., Golovach, P.A., Otachi, Y., van Leeuwen, E.J.: Parameterized complexity of the spanning tree congestion problem (submitted)"},{"key":"44_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"44_CR5","first-page":"273","volume":"67","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combin.\u00a067, 273\u2013281 (2003)","journal-title":"Ars Combin."},{"key":"44_CR6","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":"44_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math.\u00a0101, 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"44_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)"},{"key":"44_CR9","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":"44_CR10","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. North Holland, Amsterdam (2004)","edition":"2"},{"key":"44_CR11","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. Comput. J.\u00a051, 326\u2013362 (2008)","journal-title":"Comput. J."},{"key":"44_CR12","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":"44_CR13","unstructured":"Kozawa, K., Otachi, Y.: Spanning tree congestion of rook\u2019s graphs. Discuss. Math. Graph Theory (to appear)"},{"key":"44_CR14","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":"44_CR15","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":"44_CR16","unstructured":"Law, H.F., Ostrovskii, M.I.: Spanning tree congestion of some product graphs. Indian J. Math. (to appear)"},{"key":"44_CR17","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":"44_CR18","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":"44_CR19","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":"44_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-16926-7_3","volume-title":"Graph Theoretic Concepts in Computer Science","author":"Y. Otachi","year":"2010","unstructured":"Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.: Complexity results for the spanning tree congestion problem. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 3\u201314. Springer, Heidelberg (2010)"},{"key":"44_CR21","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"},{"key":"44_CR22","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"J.H. Yan","year":"1996","unstructured":"Yan, J.H., Chen, J.J., Chang, G.J.: Quasi-threshold graphs. Discrete Appl. Math.\u00a069, 247\u2013255 (1996)","journal-title":"Discrete Appl. Math."},{"key":"44_CR23","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Mech.\u00a02, 77\u201379 (1981)","journal-title":"SIAM J. Alg. Disc. Mech."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T01:18:54Z","timestamp":1558574334000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}