{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:56Z","timestamp":1759063496678},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642132834"},{"type":"electronic","value":"9783642132841"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13284-1_19","type":"book-chapter","created":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T07:43:53Z","timestamp":1275723833000},"page":"237-246","source":"Crossref","is-referenced-by-count":4,"title":["A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs"],"prefix":"10.1007","author":[{"given":"Michael J.","family":"Dinneen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masoud","family":"Khosravani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"19_CR1","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1287\/opre.1070.0432","volume":"55","author":"R. Baldacci","year":"2007","unstructured":"Baldacci, R., Dell\u2019Amico, M., Salazar Gonz\u00e1lez, J.: The capacitated-ring-star problem. Operations Research\u00a055(6), 1147\u20131162 (2007)","journal-title":"Operations Research"},{"issue":"6","key":"19_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(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-540-72951-8_3","volume-title":"Structural Information and Communication Complexity","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: Treewidth: Structure and algorithms. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol.\u00a04474, pp. 11\u201325. Springer, Heidelberg (2007)"},{"key":"19_CR4","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B)","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"19_CR5","unstructured":"Dinneen, M.J.: Practical enumeration methods for graphs of bounded pathwidth and treewidth. Technical Report CDMTCS\u2013055, Center for Discrete Mathematics and Theoretical Computer Science, Auckland (1997)"},{"key":"19_CR6","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)"},{"issue":"3","key":"19_CR7","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S.i., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J.\u00a051(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"19_CR8","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/net.10114","volume":"43","author":"M. Labb\u00e9","year":"2004","unstructured":"Labb\u00e9, M., Laporte, G., Mart\u00edn, I.R., Gonz\u00e1lez, J.J.S.: The ring star problem: Polyhedral analysis and exact algorithm. Networks\u00a043(3), 177\u2013189 (2004)","journal-title":"Networks"},{"issue":"3","key":"19_CR9","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.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms\u00a07(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"19_CR10","unstructured":"Simonetti, L., Frota, Y., de Souza, C.C.: An exact method for the minimum caterpillar spanning problem. In: Cafieri, S., Mucherino, A., Nannicini, G., Tarissan, F., Liberti, L. (eds.) CTW, pp. 48\u201351 (2009)"},{"issue":"3","key":"19_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-007-0118-z","volume":"48","author":"J. Tan","year":"2007","unstructured":"Tan, J., Zhang, L.: The consecutive ones submatrix problem for sparse matrices. Algorithmica\u00a048(3), 287\u2013299 (2007)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13284-1_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:00:36Z","timestamp":1619784036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13284-1_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642132834","9783642132841"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13284-1_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}