{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:00Z","timestamp":1759638900253},"reference-count":38,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3766,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0166-218x(02)00389-x","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T19:10:20Z","timestamp":1052766620000},"page":"565-580","source":"Crossref","is-referenced-by-count":9,"title":["On the domination search number"],"prefix":"10.1016","volume":"127","author":[{"given":"Fedor V","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":"78","reference":[{"key":"10.1016\/S0166-218X(02)00389-X_BIB1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0012-365X(96)00205-1","article-title":"The bandwidth of a tree with k leaves is at most \u2308 k\/2 \u2309","volume":"150","author":"Ando","year":"1996","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB2","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russell, Efficient probabilistically checkable proofs and applications to approximation, in: Proceedings of the Annual ACM Symposium on Theory of Computing, Vol. 25, The Association for Computing Machinery, 1993, pp. 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB3","unstructured":"S.L. Bezrukov, Isoperimetric problems in discrete spaces, in: Extremal Problems for Finite Sets (Visegr\u00e1d, 1991), J\u00e1nos Bolyai Math. Soc., Budapest, 1994, pp. 59\u201391."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","article-title":"Graph searching, path-width, tree-width and related problems","volume":"5","author":"Bienstock","year":"1991","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB5","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","article-title":"Monotonicity in graph searching","volume":"12","author":"Bienstock","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB6","first-page":"3","article-title":"Basic graph theory: paths and circuits","volume":"Vol. 1","author":"Bondy","year":"1995"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB7","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V.B. Le, J.P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","article-title":"The bandwidth problem for graphs and matrices\u2014a survey","volume":"6","author":"Chinn","year":"1982","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480193250125","article-title":"Asteroidal triple-free graphs","volume":"10","author":"Corneil","year":"1997","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB10","doi-asserted-by":"crossref","first-page":"1284","DOI":"10.1137\/S0097539795282377","article-title":"Linear time algorithms for dominating pairs in asteroidal triple-free graphs","volume":"28","author":"Corneil","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB11","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1142\/S0218195995000246","article-title":"Searching for a mobile intruder in a corridor\u2014the open edge variant of the polygon search problem","volume":"5","author":"Crass","year":"1995","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","article-title":"Fugitive-search games on graphs and related parameters","volume":"172","author":"Dendris","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB13","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/inco.1994.1064","article-title":"The vertex separation and search number of a graph","volume":"113","author":"Ellis","year":"1994","journal-title":"Inform. Comput."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(97)00131-5","article-title":"Helicopter search problems, bandwidth and pathwidth","volume":"85","author":"Fomin","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB15","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1137\/S0895480199350477","article-title":"Interval completion and graph searching","volume":"13","author":"Fomin","year":"2000","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB16","first-page":"101","article-title":"Search problems on 1-skeletons of regular polyhedrons","volume":"7","author":"Fomin","year":"1997","journal-title":"Internat. J. Math. Game Theory Algebra"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB17","first-page":"47","article-title":"Pursuit-evasion and search problems on graphs","volume":"122","author":"Fomin","year":"1996","journal-title":"Congressus Numerantium"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/333979.333980","article-title":"Eavesdropping games","volume":"47","author":"Franklin","year":"2000","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB19","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1142\/S0218195999000273","article-title":"A visibility-based pursuit-evasion problem","volume":"9","author":"Guibas","year":"1999","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB20","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","article-title":"Optimal numberings and isoperimetric problem on graphs","volume":"8","author":"Harper","year":"1966","journal-title":"J. Combin. Theory"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","article-title":"Searching and pebbling","volume":"47","author":"Kirousis","year":"1986","journal-title":"Theore. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB22","doi-asserted-by":"crossref","unstructured":"T. Kloks, D. Kratsch, H. M\u00fcller, Approximating the bandwidth of asteroidal-triple free graphs, Forschungsergebnisse Math\/95\/6, Friedrich Schiller Universit\u00e4t, Jena, Germany, 1995.","DOI":"10.1007\/3-540-60313-1_161"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB23","unstructured":"T. Kloks, D. Kratsch, 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":"10.1016\/S0166-218X(02)00389-X_BIB24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/jagm.1998.0997","article-title":"Approximating the bandwidth of asteroidal-triple free graphs","volume":"32","author":"Kloks","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB25","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/151261.151263","article-title":"Recontamination does not help to search a graph","volume":"40","author":"LaPaugh","year":"1993","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB26","doi-asserted-by":"crossref","unstructured":"S.M. LaValle, B.H. Simov, G. Slutzki, An algorithm for searching a polygonal region with a flashlight, in: Proceedings of the 16th Annual Symposium on Computational Geometry, Hong Kong, 2000, New York, 2000, ACM, pp. 260\u2013269 (electronic).","DOI":"10.1145\/336154.336212"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB27","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1142\/S0218195900000127","article-title":"Searching a polygonal room with one door by a 1-searcher","volume":"10","author":"Lee","year":"2000","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB28","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximation problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB29","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0606044","article-title":"Topological bandwidth","volume":"6","author":"Makedon","year":"1985","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB30","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","article-title":"On minimizing width in linear layouts","volume":"23","author":"Makedon","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB31","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","article-title":"Min cut is NP-complete for edge weighted trees","volume":"58","author":"Monien","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB32","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","article-title":"Characterizations and algorithmic applications of chordal graph embeddings","volume":"79","author":"Parra","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB33","first-page":"50","article-title":"On some problem of guaranteed search","volume":"27","author":"Petrov","year":"1994","journal-title":"Vestn. St.Petersb. Univ. Math"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB34","unstructured":"N.N. Petrov, I. Ture, A pursuit problem on a graph, Vestn. Leningr. Univ., Math. (translation from Vestn. Leningr. Univ., Ser. I 4, 1990, 12\u201318) 23 (1990) 12\u201319."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB35","doi-asserted-by":"crossref","unstructured":"R. Raz, 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":"10.1016\/S0166-218X(02)00389-X_BIB36","series-title":"Surveys in Combinatorics","first-page":"153","article-title":"Graph minors\u2014a survey","author":"Robertson","year":"1985"},{"key":"10.1016\/S0166-218X(02)00389-X_BIB37","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1137\/0402013","article-title":"Optimal algorithms for a pursuit-evasion problem in grids","volume":"2","author":"Sugihara","year":"1989","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(02)00389-X_BIB38","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1137\/0221051","article-title":"Searching for a mobile intruder in a polygonal region","volume":"21","author":"Suzuki","year":"1992","journal-title":"SIAM J. Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0200389X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0200389X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T02:57:03Z","timestamp":1583981823000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X0200389X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0166218X0200389X"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00389-x","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}