{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:49Z","timestamp":1725663409998},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540549451"},{"type":"electronic","value":"9783540466000"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54945-5_50","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T23:20:26Z","timestamp":1330212026000},"page":"61-71","source":"Crossref","is-referenced-by-count":2,"title":["Mixed-searching and proper-path-width"],"prefix":"10.1007","author":[{"given":"Atsushi","family":"Takahashi","sequence":"first","affiliation":[]},{"given":"Shuichi","family":"Ueno","sequence":"additional","affiliation":[]},{"given":"Yoji","family":"Kajitani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"2","key":"9_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. G. Corneil, and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8(2), pp. 277\u2013284, April 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"2","key":"9_CR2","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D. Bienstock","year":"1991","unstructured":"D. Bienstock and P. Seymour, Monotonicity in graph searching; Journal of Algorithms, 12(2), pp. 239\u2013245, 1991.","journal-title":"Journal of Algorithms"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender and T. Kloks, Better algorithm for the pathwidth and treewidth of graphs, 1991, manuscript.","DOI":"10.1007\/3-540-54233-7_162"},{"issue":"5","key":"9_CR4","first-page":"72","volume":"6","author":"R. L. Breisch","year":"1967","unstructured":"R. L. Breisch, An intuitive approach to speleotopology, Southwestern Cavers (published by the Southwestern Region of the National Speleological Society), 6(5), pp. 72\u201378, 1967.","journal-title":"Southwestern Cavers"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"D. S. Johnson","year":"1987","unstructured":"D. S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, 8, pp. 285\u2013303, 1987.","journal-title":"Journal of Algorithms"},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L. M. Kirousis","year":"1985","unstructured":"L. M. Kirousis and C. H. Papadimitriou, Interval graphs and searching, Discrete Mathematics, 55, pp. 181\u2013184, 1985.","journal-title":"Discrete Mathematics"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L. M. Kirousis","year":"1986","unstructured":"L. M. Kirousis and C. H. Papadimitriou, Searching and pebbling, Theoretical Computer Science, 47, pp. 205\u2013218, 1986.","journal-title":"Theoretical Computer Science"},{"key":"9_CR8","unstructured":"A. LaPaugh, Recontamination does not help to search a graph, Technical Report, Electrical Engineering and Computer Science Department, Princeton University, 1983."},{"issue":"1","key":"9_CR9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"M. Megiddo","year":"1988","unstructured":"M. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, Journal of the Association for Computing Machinery, 35(1), pp. 18\u201344, January 1988.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-7091-9076-0_2","volume-title":"Computational Graph Theory","author":"R. H. M\u00f6hring","year":"1990","unstructured":"R. H. M\u00f6hring, Graph problems related to gate matrix layout and PLA folding, in G. Tinhofer, E. Mayr, H. Noltemeier, and M. Syslo, editors, Computational Graph Theory, pp. 17\u201351, Springer-Verlag, Wien New York, 1990."},{"key":"9_CR11","first-page":"426","volume-title":"Theory and Applications of Graphs","author":"T. D. Parsons","year":"1976","unstructured":"T. D. Parsons, Pursuit-evasion in a graph, in Y. Alavi and D. Lick, editors, Theory and Applications of Graphs, pp. 426\u2013441, Springer-Verlag, Berlin, 1976."},{"issue":"35","key":"9_CR12","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"B","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P. D. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B(35), pp. 39\u201361, 1983.","journal-title":"Journal of Combinatorial Theory, Series"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, 1986, preprint.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"9_CR14","unstructured":"N. Robertson and P. D. Seymour, Graph minors. XVI. Wagner's conjecture, 1987, preprint."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/978-3-642-46908-4_70","volume-title":"Topics in Combinatorics and Graph Theory","author":"P. Scheffler","year":"1990","unstructured":"P. Scheffler, A linear algorithm for the pathwidth of trees, in R. Bodendiek and R. Henn, editors, Topics in Combinatorics and Graph Theory, pp. 613\u2013620, Physica-Verlag, Heidelberg, 1990."},{"key":"9_CR16","unstructured":"S. Shinoda, On some problems of graphs \u2014 including Kajitani's conjecture and its solution \u2014, in Proc. of 2nd Karuizawa Workshop on Circuits and Systems, pp. 414\u2013418, 1989, in Japanese."},{"key":"9_CR17","unstructured":"A. Takahashi, S. Ueno, and Y. Kajitani, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, to appear in Annals of discrete mathematics (Proceedings of 2nd Japan conference on graph theory and combinatorics, 1990). Also: SIGAL 91-19-3, IPSJ, 1991."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"A. Takahashi, S. Ueno, and Y. Kajitani, Mixed-searching and proper-path-width, Technical Report SIGAL 91-22-7, IPSJ, 1991.","DOI":"10.1007\/3-540-54945-5_50"}],"container-title":["Lecture Notes in Computer Science","ISA'91 Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54945-5_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:52Z","timestamp":1605646612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54945-5_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540549451","9783540466000"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-54945-5_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}