{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:17Z","timestamp":1725488957729},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540411833"},{"type":"electronic","value":"9783540400646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40064-8_16","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T00:25:42Z","timestamp":1186878342000},"page":"161-171","source":"Crossref","is-referenced-by-count":0,"title":["On the Domination Search Number"],"prefix":"10.1007","author":[{"given":"Fedor","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,7,18]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"K. Ando, A. Kaneko and S. Gervacio, The bandwidth of a tree with k leaves is at most [k\/2], Discrete Mathematics, 150 (1996), pp. 403-406.","DOI":"10.1016\/0012-365X(96)00205-1"},{"key":"16_CR2","first-page":"33","volume":"5","author":"D. Bienstock","year":"1991","unstructured":"D. Bienstock, Graph searching, path-width, tree-width and related problems (asurvey), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 5 (1991), pp. 33\u201349.","journal-title":"Graph searching, path-width, tree-width and related problems (asurvey)"},{"key":"16_CR3","unstructured":"J. A. Bondy, Basic graph theory: Paths and circuits, in Handbook of Combinatorics, Vol. 1, R. L. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz,eds., Elsevier Science B.V., 1995, pp. 3\u2013110."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le and J. P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"D. G. Corneil","year":"1999","unstructured":"D. G. Corneil, S. Olariu and L. K. Stewart, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM Journal on Computing, 28 (1999), pp. 1284\u20131297.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D. G. Corneil","year":"1997","unstructured":"D. G. Corneil, S. Olariu and L. K. Stewart, Asteroidal triple-free graphs, SIAM Journal on Discrete Mathematics, 10 (1997), pp. 399\u2013430.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N. D. Dendris","year":"1997","unstructured":"N. D. Dendris, L. M. Kirousis and D. M. Thilikos, Fugitive-search games on graphs and related parameters, Theoretical Computer Science, 172 (1997), pp. 233\u2013254.","journal-title":"Theoretical Computer Science"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J. A. Ellis","year":"1994","unstructured":"J. A. Ellis, I. H. Sudborough and J. Turner, The vertex separation and search number of a graph, Information and Computation, 113 (1994), pp. 50\u201379.","journal-title":"Information and Computation"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(97)00131-5","volume":"85","author":"F. Fomin","year":"1998","unstructured":"F. Fomin, Helicopter search problems, bandwidth and pathwidth, Discrete Applied Mathematics, 85 (1998), pp. 59\u201371.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR10","first-page":"70","volume":"3","author":"F. Fomin","year":"1998","unstructured":"F. Fomin, Search demands and interval graphs (in russian), Discrete Analysis and Operations Research, Series 1, 3 (1998), pp. 70\u201379.","journal-title":"Discrete Analysis and Operations Research"},{"key":"16_CR11","first-page":"47","volume":"122","author":"F. V. Fomin","year":"1996","unstructured":"F. V. Fomin and N. N. Petrov, Pursuit-evasion and search problems on graphs, Congressus Numerantium, 122 (1996), pp. 47\u201358.","journal-title":"Congressus Numerantium"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"M. Franklin, Z. Galil and M. Yung, Eavesdropping games: A graph-theoretic approach to privacy in distributed systems, in Proceedings of the 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, 1993, IEEE, pp. 670\u2013679.","DOI":"10.1109\/SFCS.1993.366820"},{"key":"16_CR13","doi-asserted-by":"publisher","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 (1986), pp. 205\u2013218.","journal-title":"Theoretical Computer Science"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/jagm.1998.0997","volume":"32","author":"T. Kloks","year":"1999","unstructured":"T. Kloks, D. Kratsch and H. M\u00fcller, Approximating the bandwidth of asteroidal-triple free graphs, Journal of Algorithms, 32 (1999), pp. 41\u201357.","journal-title":"Journal of Algorithms"},{"key":"16_CR15","volume-title":"Technical Report Math\/Inf\/97\/22","author":"T. Kloks","year":"1997","unstructured":"T. Kloks, D. Kratsch and H. M\u00fcller, On the structure of graphs with bounded asteroidal number, Technical Report Math\/Inf\/97\/22, Friedrich-Schiller-Universit\u00e4t, Jena, Germany, 1997."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"F. S. Makedon","year":"1985","unstructured":"F. S. Makedon, C. H. Papadimitriou and I. H. Sudborough, Topological band-width, SIAM Journal on Algebraic and Discrete Methods, 6 (1985), pp. 418\u2013444.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","volume":"23","author":"F. S. Makedon","year":"1989","unstructured":"F. S. Makedon and I. H. Sudborough, On minimizing width in linear layouts, Discrete Applied Mathematics, 23 (1989), pp. 243\u2013265.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"A. Parra and P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics, 79 (1997), pp. 171\u2013188.","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra, A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, in Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 29, The Association for Computing Machinery, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. D. Seymour, Graph minors-a survey, in Surveys in Combinatorics, I. Anderson, ed., Cambridge Univ. Press, 1985, pp. 153\u2013171.","DOI":"10.1017\/CBO9781107325678.009"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1137\/0402013","volume":"2","author":"K. Sugihara","year":"1989","unstructured":"K. Sugihara and I. Suzuki, Optimal algorithms for a pursuit-evasion problem in grids, SIAM Journal on Discrete Mathematics, 2 (1989), pp. 126\u2013143.","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40064-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:40:03Z","timestamp":1556739603000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40064-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540411833","9783540400646"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-40064-8_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}