{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:58:30Z","timestamp":1725551910860},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540311980"},{"type":"electronic","value":"9783540322177"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_17","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T11:37:18Z","timestamp":1136461038000},"page":"197-206","source":"Crossref","is-referenced-by-count":3,"title":["Graph Searching and Search Time"],"prefix":"10.1007","author":[{"given":"Franz J.","family":"Brandenburg","sequence":"first","affiliation":[]},{"given":"Stephanie","family":"Herrmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of Finding Embeddings in a k-Tree. SIAM J. Alg. Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR2","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","volume-title":"Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey)","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey). DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a05, pp. 33\u201349. American Mathematical Society, Providence (1991)"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D., Seymour, P.D.: Monotonicity in Graph Searching. J. Algorithms\u00a012, 239\u2013245 (1991)","journal-title":"J. Algorithms"},{"key":"17_CR4","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":"17_CR5","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and Pathwidth of Permutation Graphs. SIAM J. Discrete Math.\u00a08, 606\u2013616 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.: The Pathwidth and Treewidth of Cographs. SIAM J. Discrete Math.\u00a06, 181\u2013188 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.tcs.2004.09.040","volume":"332","author":"F.J. Brandenburg","year":"2005","unstructured":"Brandenburg, F.J., Skodinis, K.: Finite Graph Automata for Linear and Boundary Graph Languages. Theoret. Computer Sci.\u00a0332, 199\u2013232 (2005)","journal-title":"Theoret. Computer Sci."},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(91)90018-D","volume":"40","author":"R.S. Chang","year":"1991","unstructured":"Chang, R.S.: Single Step Graph Search Problem. Inform. Proc. Letters\u00a040, 107\u2013111 (1991)","journal-title":"Inform. Proc. Letters"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N.D. Dendris","year":"1997","unstructured":"Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-Search Games on Graphs and Related Parameters. Theoret. Computer Sci.\u00a0172, 233\u2013254 (1997)","journal-title":"Theoret. Computer Sci."},{"key":"17_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.: The Vertex Separation and Search Number of a Graph. Inform. and Comput.\u00a0113, 50\u201379 (1994)","journal-title":"Inform. and Comput."},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(97)00131-5","volume":"85","author":"F. Fomin","year":"1998","unstructured":"Fomin, F.: Helicopter Search Problems, Bandwidth and Pathwidth. Discrete Appl. Math.\u00a085, 59\u201371 (1998)","journal-title":"Discrete Appl. Math."},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0166-218X(02)00297-4","volume":"135","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V.: Searching Expenditure and Interval Graphs. Discrete Appl. Math.\u00a0135, 97\u2013104 (2004)","journal-title":"Discrete Appl. Math."},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1137\/S0895480199350477","volume":"13","author":"F.V. Fomin","year":"2000","unstructured":"Fomin, F.V., Golovach, P.A.: Graph Searching and Interval Completion. SIAM J. Discrete Math.\u00a013, 454\u2013464 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/333979.333980","volume":"47","author":"M. Franklin","year":"2000","unstructured":"Franklin, M., Galil, Z., Yung, M.: Eavesdropping Games: a Graph-Theoretic Approach to Privacy in Distributed Systems. J. Assoc. Comput. Mach.\u00a047, 225\u2013243 (2000)","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR16","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, San Francisco (1979)"},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"Gustedt, J.: On the Pathwidth of Chordal Graphs. Discrete Applied Math\u00a045, 223\u2013248 (1993)","journal-title":"Discrete Applied Math"},{"unstructured":"Hajos, G.: \u00dcber eine Art von Graphen. Mathematische Nachrichten\u00a011 (1957)","key":"17_CR18"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The Vertex Separation Number of a Graph Equals Its Path-Width. Inform. Proc. Letters\u00a042, 345\u2013350 (1992)","journal-title":"Inform. Proc. Letters"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L.M. Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval Graphs and Searching. Discrete Appl. Math.\u00a055, 181\u2013184 (1985)","journal-title":"Discrete Appl. Math."},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L.M. Kirousis","year":"1986","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Searching and Pebbling. Theoret. Comput. Sci.\u00a047, 205\u2013218 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth - Computations and Applications","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"17_CR23","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A.S. LaPaugh","year":"1993","unstructured":"LaPaugh, A.S.: Recontamination Does Not Help to Search a Graph. J. Assoc. Comput. Mach.\u00a040, 224\u2013245 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"Lengauer, T.: Black-White Pebbles and Graph Separation. Acta Inform.\u00a016, 465\u2013475 (1981)","journal-title":"Acta Inform."},{"key":"17_CR25","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The Complexity of Searching a Graph. J. Assoc. Comput. Mach.\u00a035, 18\u201344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR26","first-page":"426","volume-title":"Theory and Application in Graphs","author":"T.D. Parsons","year":"1976","unstructured":"Parsons, T.D.: Pursit-Evasion in Graphs. In: Theory and Application in Graphs, pp. 426\u2013441. Springer, Berlin (1976)"},{"key":"17_CR27","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors I. Excluding a Forest. J. Combin. Theory Ser. B\u00a035, 39\u201361 (1983)","journal-title":"Excluding a Forest. J. Combin. Theory Ser. B"},{"key":"17_CR28","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P.D. Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph Searching and a Min-Max Theorem for Tree-Width. Journal of Combinatorial Theory, Series B\u00a058, 22\u201333 (1993)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"17_CR29","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0196-6774(02)00225-0","volume":"47","author":"K. Skodinis","year":"2003","unstructured":"Skodinis, K.: Construction of Linear Tree-Layouts which Are Optimal with Respect to Vertex Vertex Separation in Linear Time. J. Algorithms\u00a047, 40\u201359 (2003)","journal-title":"J. Algorithms"},{"key":"17_CR30","volume-title":"Computational Complexity","author":"K. Wagner","year":"1986","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Reidel, Dordrecht (1986)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T02:53:06Z","timestamp":1626922386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11611257_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}