{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:01:55Z","timestamp":1725494515700},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676904"},{"type":"electronic","value":"9783540449850"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44985-x_11","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T20:17:33Z","timestamp":1194985053000},"page":"111-124","source":"Crossref","is-referenced-by-count":2,"title":["Embeddings of k-Connected Graphs of Pathwidth k"],"prefix":"10.1007","author":[{"given":"Arvind","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Proskurowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"11_CR1","unstructured":"A. Amir and M. Farach. Efficient 2-dimensional approximate matching of non-rectangular figures. In Proceedings of the Second Annual ACM-SIAM Symposiumon Discrete Algorithms, pages 212\u2013223, 1991."},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U.S.R. Murty. Graph Theory with Applications. North-Holland, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pages 226\u2013234, 1993.","DOI":"10.1145\/167088.167161"},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R. G. Downey","year":"1995","unstructured":"R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness. I. Basic results. SIAM Journal on Computing, 24(4):873\u2013921,August 1995.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"A. Dessmark, A. Lingas, and A. Proskurowski. Faster algorithms for subgraph isomorphism of k-connected partial k-trees. In Proceedings of the Fourth Annual European Symposium on Algorithms, pages 501\u2013513, 1996. To appear, Algorithmica.","DOI":"10.1007\/3-540-61680-2_78"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"A. Gupta and N. Nishimura. Sequential and parallel algorithms for embedding problems on classes of partial k-trees. In Proceedings of the Fourth Scandinavian Workshop on Algorithm Theory, pages 172\u2013182, 1994.","DOI":"10.1007\/3-540-58218-5_16"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1006\/jagm.1995.1006","volume":"18","author":"A. Gupta","year":"1995","unstructured":"A. Gupta and N. Nishimura. The parallel complexity of tree embedding problems. Journal of Algorithms, 18(1):176\u2013200, 1995.","journal-title":"Journal of Algorithms"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(96)00046-1","volume":"164","author":"A. Gupta","year":"1996","unstructured":"A. Gupta and N. Nishimura. The complexity of subgraph isomorphism for classes of partial k-trees. Theoretical Computer Science, 164:287\u2013298, 1996.","journal-title":"Theoretical Computer Science"},{"key":"11_CR9","unstructured":"A. Gupta and N. Nishimura. Topological embedding of k-connected partial k-trees. submitted, 1998."},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/S0097539793258143","volume":"25","author":"H. Kaplan","year":"1996","unstructured":"H. Kaplan and R. Shamir. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM Journal on Computing, 25(3):540\u2013561, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matoujsek","year":"1992","unstructured":"J. Matoujsek and R. Thomas. On the complexity of finding iso-and other morphisms for partial k-trees. Discrete Mathematics, 108:343\u2013364, 1992.","journal-title":"Discrete Mathematics"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0012-365X(84)90164-X","volume":"49","author":"A. Proskurowski","year":"1984","unstructured":"A. Proskurowski. Separating subgraphs in k-trees: cables and caterpillars. Discrete Mathematics, 49:275\u2013285, 1984.","journal-title":"Discrete Mathematics"},{"key":"11_CR13","unstructured":"A. Proskurowski. Maximal graphs of path-width k or searching a partial k-caterpillar. Technical Report UO-CIS-TR-89-17, University of Oregon, 1989."},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0895480192234009","volume":"11","author":"A. Proskurowski","year":"1998","unstructured":"A. Proskurowski, F. Ruskey, and M. Smith. Analysis of algorithms for listing equivalence classes of k-ary strings. SIAM Journal of Discrete Mathematics, 11(1):94\u2013109, 1998.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M. M. Syslo","year":"1982","unstructured":"M. M. Syslo. The subgraph isomorphism problem for outerplanar graphs. Theoretical Computer Science, 17:91\u201397, 1982.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(94)00160-K","volume":"137","author":"A. Takahashi","year":"1995","unstructured":"A. Takahashi, S. Ueno, and Y. Kajitani. Mixed searching and proper-pathwidth. Theoretical Computer Science, 137(2):253\u2013268, January 1995.","journal-title":"Theoretical Computer Science"},{"key":"11_CR17","series-title":"chapter Graph algorithms","volume-title":"Handbook of Theoretical Computer Science A: Algorithms and Complexity Theory","author":"J. Leeuwen van","year":"1990","unstructured":"J. van Leeuwen. Handbook of Theoretical Computer Science A: Algorithms and Complexity Theory, chapter Graph algorithms. North-Holland, Amsterdam, 1990."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44985-X_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T10:40:53Z","timestamp":1556966453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44985-X_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676904","9783540449850"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44985-x_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}