×

An annotated bibliography on guaranteed graph searching. (English) Zbl 1160.68007

Summary: Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field.

MSC:

68P10 Searching and sorting
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, I., Marshals, monotone marshals, and hypertree-width, J. Graph Theory, 47, 275-296 (2004) · Zbl 1089.68074
[2] I. Adler, G. Gottlob, M. Grohe, Hypertree-width and related hypergraph invariants, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb’05), in: Discrete Mathematics and Theoretical Computer Science, 2005, pp. 5-10; I. Adler, G. Gottlob, M. Grohe, Hypertree-width and related hypergraph invariants, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb’05), in: Discrete Mathematics and Theoretical Computer Science, 2005, pp. 5-10 · Zbl 1192.05104
[3] Aggarwal, D.; Mehta, S. K.; Deogun, J. S., Domination search on graphs with low dominating-target-number, (Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005). Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Comput. Sci., vol. 3787 (2005), Springer: Springer Berlin), 28-37 · Zbl 1126.68513
[4] Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1-11 (1984) · Zbl 0539.05052
[5] Alpern, S.; Gal, S., The theory of search games and rendezvous, (International Series in Operations Research & Management Science, vol. 55 (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA) · Zbl 1034.91017
[6] Alspach, B., Searching and sweeping graphs: a brief survey, Matematiche (Catania), 59, 5-37 (2006) · Zbl 1195.05019
[7] Alspach, B.; Dyer, D.; Hanson, D.; Yang, B., Arc searching digraphs without jumping, (Proceedings of the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007). Proceedings of the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007), Lecture Notes in Computer Sci., vol. 4616 (2007), Springer), 354-365 · Zbl 1175.05123
[8] Alspach, B.; Dyer, D.; Hanson, D.; Yang, B., Lower bounds on edge searching, (Proceedings of the 1st International Symposium Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007). Proceedings of the 1st International Symposium Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007), Lecture Notes in Computer Sci., vol. 4614 (2007), Springer), 516-527 · Zbl 1176.91017
[9] Andreae, T., Note on a pursuit game played on graphs, Discrete Appl. Math., 9, 111-115 (1984) · Zbl 0548.05056
[10] Andreae, T., On a pursuit game played on graphs for which a minor is excluded, J. Comb. Theory Ser., B, 41, 37-47 (1986) · Zbl 0641.90110
[11] Andrianov, V. Y.; Petrov, N. N., Graph searching problems with the counteraction, (Game theory and applications, Vol. X. Game theory and applications, Vol. X, Game Theory Appl., vol. 10 (2005), Nova Sci. Publ.: Nova Sci. Publ. Hauppauge, NY), 1-12 · Zbl 1091.91013
[12] Andrianov, V. Y.; Petrov, N. N., Search under counteraction, Proc. Steklov Inst. Math., S16-S24 (2005) · Zbl 1165.91337
[13] Anstee, R. P.; Farber, M., On bridged graphs and cop-win graphs, J. Comb. Theory Ser. B, 44, 22-28 (1988) · Zbl 0654.05049
[14] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebr. Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022
[15] Azamov, A.; Norzhigitov, K., On a minimax dynamic problem of search on graphs, Uzbek. Mat. Zh., 13-18 (1991)
[16] Barát, J., Directed path-width and monotonicity in digraph searching, Graphs Combin., 22, 161-172 (2006) · Zbl 1138.05069
[17] Barrière, L.; Flocchini, P.; Fraigniaud, P.; Santoro, N., Capture of an intruder by mobile agents, (Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures (SPAA 2002) (2002), ACM Press), 200-209
[18] Barrière, L.; Fraigniaud, P.; Santoro, N.; Thilikos, D. M., Searching is not jumping, (Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003). Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), Lecture Notes in Comput. Sci., vol. 2880 (2003), Springer), 34-45 · Zbl 1255.68105
[19] Berarducci, A.; Intrigila, B., On the cop number of a graph, Adv. in Appl. Math., 14, 389-403 (1993) · Zbl 0801.90150
[20] Berwanger, D.; Dawar, A.; Hunter, P.; Kreutzer, S., Dag-width and parity games, (Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2006). Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2006), Lecture Notes in Comput. Sci., vol. 3884 (2006), Springer), 524-536 · Zbl 1136.68447
[21] Bienstock, D., Graph searching, path-width, tree-width and related problems (a survey), (Reliability of computer and communication networks (New Brunswick, NJ, 1989). Reliability of computer and communication networks (New Brunswick, NJ, 1989), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 5 (1991), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 33-49 · Zbl 0777.05090
[22] Bienstock, D.; Robertson, N.; Seymour, P.; Thomas, R., Quickly excluding a forest, J. Comb. Theory Ser., B, 52, 274-283 (1991) · Zbl 0763.05023
[23] Bienstock, D.; Seymour, P., Monotonicity in graph searching, J. Algorithms, 12, 239-245 (1991) · Zbl 0760.05081
[24] Blin, L.; Fraigniaud, P.; Nisse, N.; Vial, S., Distributed chasing of network intruders, (Proceedings of the 13th International Colloquium Structural Information and Communication Complexity (SIROCCO 2006). Proceedings of the 13th International Colloquium Structural Information and Communication Complexity (SIROCCO 2006), Lecture Notes in Comput. Sci., vol. 4056 (2006), Springer), 70-84 · Zbl 1222.68122
[25] Bodlaender, H. L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[26] Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148
[27] Bodlaender, H. L.; Thilikos, D. M., Computing small search numbers in linear time, (Proceedings of the First International Workshop on Parameterized and Exact Computation (IWPEC 2004). Proceedings of the First International Workshop on Parameterized and Exact Computation (IWPEC 2004), Lecture Notes in Comput. Sci., vol. 3162 (2004), Springer), 37-48 · Zbl 1104.68079
[28] Brandenburg, F.-J.; Herrmann, S., Graph searching and search time, (Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2006). Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2006), Lecture Notes in Comput. Sci., vol. 3831 (2006), Springer), 197-206 · Zbl 1175.68197
[29] Breisch, R., An intuitive approach to speleotopology, southwestern Cavers (A publication of the Southwestern Region of the National Speleological Society), VI, 72-78 (1967)
[30] Brightwell, G. R.; Winkler, P., Gibbs measures and dismantlable graphs, J. Combin. Theory Ser., B, 78, 141-166 (2000) · Zbl 1030.05101
[31] Chang, R. S., Single step graph search problem, Inf. Process. Lett., 40, 107-111 (1991) · Zbl 0748.68043
[32] Chastand, M.; Laviolette, F.; Polat, N., On constructible graphs, infinite bridged graphs and weakly cop-win graphs, Discrete Math., 224, 61-78 (2000) · Zbl 0961.05066
[33] Chepoi, V., Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory Ser., B, 69, 97-100 (1997) · Zbl 0873.05060
[34] Clarke, N. E., A game of cops and robber played with partial information, (Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., vol. 166 (2004)), 145-159 · Zbl 1063.05113
[35] Clarke, N. E.; Connon, E. L., Cops, robber, and alarms, Ars Combin., 81, 283-296 (2006) · Zbl 1174.91326
[36] Clarke, N. E.; Nowakowski, R. J., Cops, robber, and photo radar, Ars Combin., 56, 97-103 (2000) · Zbl 0994.05145
[37] Clarke, N. E.; Nowakowski, R. J., Cops, robber and traps, Util. Math., 60, 91-98 (2001) · Zbl 1011.05052
[38] Clarke, N. E.; Nowakowski, R. J., A tandem version of the cops and robber game played on products of graphs, Discuss. Math. Graph Theory, 25, 241-249 (2005) · Zbl 1148.91009
[39] Clarke, N. E.; Nowakowski, R. J., Tandem-win graphs, Discrete Math., 299, 56-64 (2005) · Zbl 1073.05060
[40] Crass, D.; Suzuki, I.; Yamashita, M., Searching for a mobile intruder in a corridor—the open edge variant of the polygon search problem, Internat. J. Comput. Geom. Appl., 5, 397-412 (1995) · Zbl 0838.68111
[41] Dawes, R. W., Some pursuit-evasion problems on grids, Inf. Process. Lett., 43, 241-247 (1992) · Zbl 0767.90099
[42] Dendris, N. D.; Kirousis, L. M.; Thilikos, D. M., Fugitive-search games on graphs and related parameters, Theoret. Comput. Sci., 172, 233-254 (1997) · Zbl 0903.68052
[43] Deo, N.; Nikoloski, Z., The game of cops and robbers on graphs: a model for quarantining cyber attacks, (Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., vol. 162 (2003)), 193-215 · Zbl 1091.68555
[44] Ellis, J.; Markov, M., Computing the vertex separation of unicyclic graphs, Inf. Comput., 192, 123-161 (2004) · Zbl 1069.68077
[45] Ellis, J. A.; Sudborough, I. H.; Turner, J. S., The vertex separation and search number of a graph, Inf. Comput., 113, 50-79 (1994) · Zbl 0942.68641
[46] Fitzpatrick, S. L.; Nowakowski, R. J., Copnumber of graphs with strong isometric dimension two, Ars Combin., 59, 65-73 (2001) · Zbl 1066.05118
[47] Flocchini, P.; Huang, M. J.; Luccio, F. L., Contiguous search in the hypercube for capturing an intruder, (Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS 2005) IPDPS (2005), IEEE Computer Society)
[48] Flocchini, P.; Huang, M. J.; Luccio, F. L., Decontamination of chordal rings and tori using mobile agents, Internat. J. Found. Comput. Sci., 18, 547-564 (2007)
[49] P. Flocchini, M.J. Huang, F.L. Luccio, Decontamination of hypercubes by mobile agents, Networks, Published Online: 25 February 2008; P. Flocchini, M.J. Huang, F.L. Luccio, Decontamination of hypercubes by mobile agents, Networks, Published Online: 25 February 2008 · Zbl 1194.68236
[50] Fomin, F. V., A search problem on a graph under restriction of the velocity, Vestnik St. Petersburg Univ. Math., 27, 50-54 (1994) · Zbl 0854.68026
[51] Fomin, F. V., The search for the evader on 3-minimal trees, Vestnik St. Petersburg Univ. Math., 28, 56-60 (1995) · Zbl 0883.05122
[52] Fomin, F. V., Search problem on trees, Vestnik St. Petersburg Univ. Math., 28, 36-39 (1995) · Zbl 0883.90148
[53] Fomin, F. V., Almost discrete search programs on graphs, Vestnik St. Petersburg Univ. Math., 30, 44-49 (1997), 1998 · Zbl 1035.91501
[54] Fomin, F. V., Helicopter search problems, bandwidth and pathwidth, Discrete Appl. Math., 85, 59-70 (1998) · Zbl 0901.68042
[55] Fomin, F. V., Note on a helicopter search problem on graphs, Discrete Appl. Math., 95, 241-249 (1999) · Zbl 0947.91015
[56] Fomin, F. V., A generalization of the graph bandwidth, Vestnik St. Petersburg Univ. Math., 34, 15-19 (2001)
[57] Fomin, F. V.; Fraigniaud, P.; Nisse, N., Nondeterministic graph searching: From pathwidth to treewidth, (Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Lecture Notes in Comput. Sci., vol. 3618 (2005), Springer), 364-375 · Zbl 1156.68506
[58] Fomin, F. V.; Golovach, P. A., Graph searching and interval completion, SIAM J. Discrete Math., 13, 454-464 (2000) · Zbl 0972.05047
[59] Fomin, F. V.; Golovach, P. A.; Petrov, N. N., Search problems on 1-skeletons of regular polyhedrons, Int. J. Math. Game Theory Algebra, 7, 101-111 (1998) · Zbl 0904.90091
[60] Fomin, F. V.; Heggernes, P.; Mihai, R., Mixed search number and linear-width of interval and split graphs, (Procceeding of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). Procceeding of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Comput. Sci., vol. 4769 (2007), Springer), 304-315 · Zbl 1141.68526
[61] Fomin, F. V.; Heggernes, P.; Telle, J. A., Graph searching, elimination trees, and a generalization of bandwidth, Algorithmica, 41, 73-87 (2005) · Zbl 1082.68082
[62] Fomin, F. V.; Kratsch, D.; Müller, H., On the domination search number, Discrete Appl. Math., 127, 565-580 (2003) · Zbl 1019.68076
[63] Fomin, F. V.; Petrov, N. N., Pursuit-evasion and search problems on graphs, (Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., vol. 122 (1996)), 47-58 · Zbl 0897.05079
[64] Fomin, F. V.; Thilikos, D. M., On the monotonicity of games generated by symmetric submodular functions, Discrete Appl. Math., 131, 323-335 (2003) · Zbl 1069.91019
[65] Fomin, F. V.; Thilikos, D. M.; Todinca, I., Connected graph searching in outerplanar graphs, Electronic Notes in Discrete Mathematics, 22, 213-216 (2005), 7th International Colloquium on Graph Theory. Short communication. · Zbl 1200.68170
[66] Fraigniaud, P.; Fomin, F. V.; Thilikos, D. M., Connected branch decomposition and graph searching, (SIAM Conference on Discrete Mathematics (2006))
[67] Fraigniaud, P.; Nisse, N., Connected treewidth and connected graph searching, (Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006). Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Lecture Notes in Comput. Sci., vol. 3887 (2006), Springer), 479-490 · Zbl 1145.68473
[68] Fraigniaud, P.; Nisse, N., Monotony properties of connected visible graph searching, (Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006). Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Comput. Sci., vol. 4271 (2006), Springer), 229-240 · Zbl 1167.68407
[69] Frankl, P., Cops and robbers in graphs with large girth and Cayley graphs, Discrete Appl. Math., 17, 301-305 (1987) · Zbl 0624.05041
[70] Frankl, P., On a pursuit game on Cayley graphs, Combinatorica, 7, 67-70 (1987) · Zbl 0621.05017
[71] Franklin, M.; Galil, Z.; Yung, M., Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, J. ACM, 47, 225-243 (2000) · Zbl 1133.68469
[72] Goldstein, A. S.; Reingold, E. M., The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93-112 (1995) · Zbl 0873.68152
[73] Golovach, P. A., Equivalence of two formalizations of a search problem on a graph (Russian), Vestnik Leningrad. Univ. Mat. Mekh. Astronom., 10-14 (1989), translation in Vestnik Leningrad Univ. Math. 22 (1989), no. 1, 13-19 · Zbl 0666.90081
[74] Golovach, P. A., A topological invariant in pursuit problems (Russian), Differ. Uravn., 25, 923-929 (1989), 1097. Translation in Differ. Equ. 25 (1989), no. 6, 657-661 · Zbl 0707.90105
[75] Golovach, P. A., An extremal search problem on graphs (Russian), Vestn. Leningr. Univ. Mat. Mekh. Astron., 16-21 (1990), Translation in Vestnik Leningrad Univ. Math. 23 (1990), no. 3, 19-25 · Zbl 0704.90105
[76] Golovach, P. A., Node-search and search number of a combination of graphs, Vestn. Leningr. Univ. Mat. Mekh. Astronom., 90-91 (1990) · Zbl 0704.05050
[77] Golovach, P. A., Search number, node-search number and the vertex separator of a graph, Vestn. Leningr. Univ. Mat. Mekh. Astronom., 110-111 (1991) · Zbl 0727.90086
[78] Golovach, P. A., Minimal trees with a given search number, Kibernet. Sistem. Anal., 187, 25-31 (1992) · Zbl 0769.05030
[79] Golovach, P. A., Minimal trees with a given vertex-search number, Diskret. Mat., 4, 52-60 (1992) · Zbl 0769.05030
[80] Golovach, P. A.; Fomin, F. V., The search and the node-search number of dual graphs, Vestn. Syktyvkar. Univ. Ser. 1 Mat. Mekh. Inform., 125-136 (2001) · Zbl 0991.05098
[81] Golovach, P. A.; Petrov, N. N., The search number of a complete graph, Vestn. Leningr. Univ. Mat. Mekh. Astron., 57-60 (1986) · Zbl 0614.05058
[82] Golovach, P. A.; Petrov, N. N., The \(k\)-search number of graphs of regular polyhedra, Vestnik St. Petersburg Univ. Math., 28, 6-10 (1995) · Zbl 0893.90165
[83] Golovach, P. A.; Petrov, N. N., Some generalizations of the problem on the search number of a graph, Vestnik St. Petersburg Univ. Math., 28, 18-22 (1995) · Zbl 0883.90149
[84] Golovach, P. A.; Petrov, N. N.; Fomin, F. V., Search in graphs, Proc. Steklov Inst. Math., S90-S103 (2000) · Zbl 1118.91305
[85] Gottlob, G.; Grohe, M.; Musliu, N.; Samer, M.; Scarcello, F., Hypertree decompositions: Structure, algorithms, and applications, (Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005). Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Comput. Sci., vol. 3787 (2005), Springer), 1-15 · Zbl 1126.68516
[86] Gottlob, G.; Leone, N.; Scarcello, F., Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, J. Comput. System Sci., 66, 775-808 (2003) · Zbl 1054.68044
[87] Gottlob, G.; Miklos, Z.; Schwentick, T., Generalized hypertree decompositions: NP-hardness and tractable variants, (Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS 2007) (2007), ACM Press: ACM Press New York, NY, USA), 13-22 · Zbl 1325.68097
[88] Grohe, M.; Marx, D., Constraint solving via fractional edge covers, (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006) (2006), ACM Press: ACM Press New York, NY, USA), 289-298 · Zbl 1192.68642
[89] Guibas, L. J.; Latombe, J.-C.; Lavalle, S. M.; Lin, D.; Motwani, R., A visibility-based pursuit-evasion problem, Internat. J. Comput. Geom. Appl., 9, 471-493 (1999)
[90] Hahn, G., Cops, robbers and graphs, Tatra Mt. Math. Publ., 36, 1-14 (2007) · Zbl 1164.05063
[91] Hahn, G.; Laviolette, F.; Sauer, N.; Woodrow, R. E., On cop-win graphs, Discrete Math., 258, 27-41 (2002) · Zbl 1009.05085
[92] Hahn, G.; MacGillivray, G., A note on \(k\)-cop, \(l\)-robber games on graphs, Discrete Math., 306, 2492-2497 (2006) · Zbl 1201.91018
[93] Hamidoune, Y. O., On a pursuit game on Cayley digraphs, Eur. J. Comb., 8, 289-295 (1987) · Zbl 0639.05026
[94] Hsiao, J. Y.; Tang, C. Y.; Chang, R. S., Solving the single step graph searching problem by solving the maximum two-independent set problem, Inf. Process. Lett., 40, 283-287 (1991) · Zbl 0743.68109
[95] Hsiao, J. Y.; Tang, C. Y.; Chang, R. S., The summation and bottleneck minimization for single-step searching on weighted graphs, Inf. Sci., 74, 1-28 (1993) · Zbl 0783.68093
[96] Hsiao, J. Y.; Tang, C. Y.; Chang, R. S.; Lee, R. C.T., Single step searching in weighted block graphs, Inform. Sci., 81, 1-29 (1994) · Zbl 0837.68083
[97] Hunter, P.; Kreutzer, S., Kelly decompositions, games, and orderings, (Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) (2007), ACM Press: ACM Press New York, NY, USA), 637-644 · Zbl 1302.05068
[98] P.W. Hunter, Complexity and infinite games on finite graphs, Ph.D. Thesis, University of Cambridge, Computer Laboratory, 2007; P.W. Hunter, Complexity and infinite games on finite graphs, Ph.D. Thesis, University of Cambridge, Computer Laboratory, 2007
[99] Isaacs, R., Differential games, (A mathematical theory with applications to warfare and pursuit, control and optimization (1965), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York) · Zbl 0152.38407
[100] Johnson, T.; Robertson, N.; Seymour, P. D.; Thomas, R., Directed tree-width, J. Comb. Theory Ser., B, 82, 138-154 (2001) · Zbl 1027.05045
[101] Kapilevich, V. O.; Petrov, N. N., Search problems in graphs with counteraction, Vestnik St. Petersburg Univ. Math., 36, 28-33 (2003) · Zbl 1070.90049
[102] Kinnersley, N. G., The vertex separation number of a graph equals its path-width, Inf. Process. Lett., 42, 345-350 (1992) · Zbl 0764.68121
[103] Kirousis, L. M.; Papadimitriou, C. H., Interval graphs and searching, Discrete Math., 55, 181-184 (1985) · Zbl 0566.05056
[104] Kirousis, L. M.; Papadimitriou, C. H., Searching and pebbling, Theoret. Comput. Sci., 47, 205-218 (1986) · Zbl 0616.68064
[105] A. LaPaugh, Recontamination does not help to search a graph, tech. rep., Electrical Engineering and Computer Science Department, Princeton University, 1983; A. LaPaugh, Recontamination does not help to search a graph, tech. rep., Electrical Engineering and Computer Science Department, Princeton University, 1983
[106] LaPaugh, A. S., Recontamination does not help to search a graph, J. Assoc. Comput. Mach., 40, 224-245 (1993) · Zbl 0768.68048
[107] Lavalle, S. M.; Simov, B. H.; Slutzki, G., An algorithm for searching a polygonal region with a flashlight, Internat. J. Comput. Geom. Appl., 12, 87-113 (2002) · Zbl 1117.68527
[108] Luccio, F.; Pagli, L.; Santoro, N., Network decontamination in presence of local immunity, Internat. J. Found. Comput. Sci., 18, 457-475 (2007) · Zbl 1117.68007
[109] Lunegov, S. V.; Petrov, N. N., Some graph search problems, Vestnik St. Petersburg Univ. Math., 35, 9-12 (2002)
[110] Maamoun, M.; Meyniel, H., On a game of policemen and robber, Discrete Appl. Math., 17, 307-309 (1987) · Zbl 0615.05049
[111] Makedon, F.; Sudborough, I. H., On minimizing width in linear layouts, Discrete Appl. Math., 23, 243-265 (1989) · Zbl 0715.05012
[112] Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H., Topological bandwidth, SIAM J. Algebraic Discrete Methods, 6, 418-444 (1985) · Zbl 0573.05052
[113] Mazoit, F.; Nisse, N., Monotonicity of non-deterministic graph searching, (Proccedings of the 32th International Workshop on Graphs (WG07). Proccedings of the 32th International Workshop on Graphs (WG07), Lecture Notes in Comput. Sci., vol. 4769 (2007), Springer), 33-44 · Zbl 1141.68543
[114] Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H., The complexity of searching a graph, J. Assoc. Comput. Mach., 35, 18-44 (1988) · Zbl 0637.68081
[115] Möhring, R. H., Graph problems related to gate matrix layout and PLA folding, (Computational graph theory. Computational graph theory, Comput. Suppl., vol. 7 (1990), Springer: Springer Vienna), 17-51 · Zbl 0699.68072
[116] Moscarini, M.; Petreschi, R.; Szwarcfiter, J. L., On node searching and starlike graphs, (Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., vol. 131 (1998)), 75-84 · Zbl 0951.05090
[117] Neufeld, S.; Nowakowski, R., A game of cops and robbers played on products of graphs, Discrete Math., 186, 253-268 (1998) · Zbl 0957.91029
[118] Neufeld, S.; Nowakowski, R. J., A vertex-to-vertex pursuit game played with disjoint sets of edges, (Finite and infinite combinatorics in sets and logic (Banff, AB, 1991). Finite and infinite combinatorics in sets and logic (Banff, AB, 1991), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 411 (1993), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 299-312 · Zbl 0845.05092
[119] Neufeld, S. W., A pursuit-evasion problem on a grid, Inf. Process. Lett., 58, 5-9 (1996) · Zbl 0900.68228
[120] Nisse, Connected graph searching in chordal graphs, Discrete Appl. Math. (in press); Nisse, Connected graph searching in chordal graphs, Discrete Appl. Math. (in press) · Zbl 1211.05037
[121] Nisse, N.; Soguet, D., Graph searching with advice, (Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007). Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007), Lecture Notes in Comput. Sci., vol. 4474 (2006), Springer), 51-65 · Zbl 1201.68150
[122] Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058
[123] Nowakowski, R. J., Search and sweep numbers of finite directed acyclic graphs, Discrete Appl. Math., 41, 1-11 (1993) · Zbl 0777.05062
[124] Nowakowski, R. J.; Zeh, N., Boundary-optimal triangulation flooding, Internat. J. Comput. Geom. Appl., 16, 271-290 (2006) · Zbl 1096.65021
[125] Obdržálek, J., Dag-width: connectivity measure for directed graphs, (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006) (2006), ACM Press: ACM Press New York, NY, USA), 814-821 · Zbl 1192.05065
[126] Parsons, T. D., Pursuit-evasion in a graph, (Theory and applications of graphs. Theory and applications of graphs, Lecture Notes in Math., vol. 642 (1978), Springer: Springer Berlin), 426-441 · Zbl 0379.05026
[127] Parsons, T. D., The search number of a connected graph, (Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congress. Numer., Utilitas Math., vol. XXI (1978)), 549-554 · Zbl 0418.05022
[128] Peng, S.-L.; Ho, C.-W.; Hsu, T.-s.; Ko, M.-T.; Tang, C. Y., Edge and node searching problems on trees, Theoret. Comput. Sci., 240, 429-446 (2000) · Zbl 0945.68143
[129] Peng, S.-L.; Ko, M.-T.; Ho, C.-W.; Hsu, T.-s.; Tang, C. Y., Graph searching on some subclasses of chordal graphs, Algorithmica, 27, 395-426 (2000) · Zbl 0955.05074
[130] Petrov, N. N., A problem of pursuit in the absence of information on the pursued, Differ. Uravn., 18, 1345-1352 (1982)
[131] Petrov, N. N., Some extremal search problems on graphs, Differ. Uravn., 18, 821-827 (1982) · Zbl 0495.90097
[132] Petrov, N. N., Problems of pursuit on the 1-skeleton of a cube, Differ. Uravn., 23, 908-911 (1987) · Zbl 0692.90107
[133] Petrov, N. N., Pursuit of an invisible moving object, Differ. Uravn., 32, 1563-1565, 1583 (1996) · Zbl 0896.90188
[134] Petrov, N. N., Search problems on graphs of regular polyhedra, Diskret. Mat., 8, 108-116 (1996) · Zbl 0869.90095
[135] Petrov, N. N.; Chumanova, A. V., On certain search problems with counteraction, Vestnik St. Petersburg Univ. Math., 36, 48-52 (2003) · Zbl 1151.91363
[136] Petrov, N. N.; Fomin, F. V., Discrete search programs on graphs, Vestnik St. Petersburg Univ. Math., 32, 27-32 (1999) · Zbl 1043.91013
[137] Petrov, N. N.; Petrov, N. N., The Cossack-robber differential game, Differ. Uravn., 19, 1366-1374 (1983) · Zbl 0521.90109
[138] Petrov, N. N.; Starostina, S. A., Minimal graphs with a search number that is less than four, Vestn. Leningr. Univ. Mat. Mekh. Astronom., 105-106 (1989) · Zbl 0682.05038
[139] Petrov, N. N.; Starostina, S. A., On some problems in guaranteed search, Vestnik S.-Peterburg. Univ. Mat. Mekh. Astronom., 114-116 (1994) · Zbl 0854.68025
[140] Petrov, N. N.; Teteryatnikova, M. A., Some problems of the search on graphs with retaliation, Vestnik St. Petersburg Univ. Math., 37, 37-43 (2004) · Zbl 1107.91028
[141] Petrov, N. N.; Ture, I., A pursuit problem on a graph, Vestn. Leningr. Univ. Mat. Mekh. Astronom., 12-18 (1990) · Zbl 0717.90110
[142] Petrov, N. N.; Ture, I., Determination of the minimal number in a search group on a graph, Vestn. Leningr. Univ. Mat. Mekh. Astronom., 47-49 (1991) · Zbl 0725.90111
[143] A. Quilliot, Problémes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, 1983; A. Quilliot, Problémes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, 1983
[144] Quilliot, A., A short note about pursuit games played on a graph with a given genus, J. Comb. Theory Ser., B, 38, 89-92 (1985) · Zbl 0586.90104
[145] Quilliot, A., Some results about pursuit games on metric spaces obtained through graph theory techniques, Eur. J. Comb., 7, 55-66 (1986) · Zbl 0615.90108
[146] Richerby, D.; Thilikos, D. M., Graph searching in a crime wave, (Procceeding of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). Procceeding of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Comput. Sci., vol. 4769 (2007), Springer), 21-32 · Zbl 1141.68548
[147] Robertson, N.; Seymour, P. D., Graph minors—a survey, (Surveys in combinatorics 1985 (Glasgow, 1985). Surveys in combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser., vol. 103 (1985), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 153-171 · Zbl 0764.05069
[148] Schroeder, B. S.W., The copnumber of a graph is bounded by \(\lfloor \frac{3}{2} genus(G) \rfloor + 3\), (Categorical perspectives (Kent, OH, 1998), Trends Math. (2001), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 243-263 · Zbl 0983.05030
[149] Seymour, P. D.; Thomas, R., Graph searching and a min-max theorem for tree-width, J. Comb. Theory Ser., B, 58, 22-33 (1993) · Zbl 0795.05110
[150] Seymour, P. D.; Thomas, R., Call routing and the ratcatcher, Combinatorica, 14, 217-241 (1994) · Zbl 0799.05057
[151] Skodinis, K., Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time, J. Algorithms, 47, 40-59 (2003) · Zbl 1053.68072
[152] Smith, J. D.H., Minimal trees of given search number, Discrete Math., 66, 191-202 (1987) · Zbl 0626.05013
[153] Sugihara, K.; Suzuki, I., Optimal algorithms for a pursuit-evasion problem in grids, SIAM J. Discrete Math., 2, 126-143 (1989) · Zbl 0677.68057
[154] Sugihara, K.; Suzuki, I.; Yamashita, M., The searchlight scheduling problem, SIAM J. Comput., 19, 1024-1040 (1990) · Zbl 0711.68085
[155] Suzuki, I.; Tazoe, Y.; Yamashita, M.; Kameda, T., Searching a polygonal region from the boundary, Internat. J. Comput. Geom. Appl., 11, 529-553 (2001) · Zbl 1074.68654
[156] Suzuki, I.; Yamashita, M., Searching for a mobile intruder in a polygonal region, SIAM J. Comput., 21, 863-888 (1992) · Zbl 0757.68098
[157] Symvonis, A.; Tragoudas, S., Searching a pseudo 3-sided solid orthoconvex grid, Internat. J. Found. Comput. Sci., 4, 325-353 (1993) · Zbl 0804.68033
[158] Takahashi, A.; Ueno, S.; Kajitani, Y., Mixed searching and proper-path-width, Theoret. Comput. Sci., 137, 253-268 (1995) · Zbl 0873.68148
[159] Tan, X., Sweeping simple polygons with the minimum number of chain guards, Inf. Process. Lett., 102, 66-71 (2007) · Zbl 1184.68571
[160] Thilikos, D. M., Algorithms and obstructions for linear-width and related search parameters, Discrete Appl. Math., 105, 239-271 (2000) · Zbl 0958.05124
[161] Tošić, R., On cops and robber game, Stud. Sci. Math. Hung., 23, 225-229 (1988) · Zbl 0652.90110
[162] Wanke, E., Bounded tree-width and LOGCFL, J. Algorithms, 16, 470-491 (1994) · Zbl 0804.68048
[163] Yamashita, M.; Suzuki, I.; Kameda, T., Searching a polygonal region by a group of stationary \(k\)-searchers, Inf. Process. Lett., 92, 1-8 (2004) · Zbl 1173.68471
[164] Yamashita, M.; Umemoto, H.; Suzuki, I.; Kameda, T., Searching for mobile intruders in a polygonal region by a group of mobile searchers, Algorithmica, 31, 208-236 (2001) · Zbl 0980.68033
[165] Yang, B., Strong-mixed searching and pathwidth, J. Comb. Optim., 13, 47-59 (2007) · Zbl 1112.90039
[166] B. Yang, Y. Cao, Searching digraphs: Monotonicity and complexity, Tech. Rep. TR 2006-06, Department of Computer Science, University of Regina, Canada, 2006; B. Yang, Y. Cao, Searching digraphs: Monotonicity and complexity, Tech. Rep. TR 2006-06, Department of Computer Science, University of Regina, Canada, 2006 · Zbl 1198.68231
[167] Yang, B.; Cao, Y., Digraph strong searching: Monotonicity and complexity, (Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007). Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007), Lecture Notes in Computer Sci., vol. 4508 (2007), Springer), 37-46 · Zbl 1137.68506
[168] Yang, B.; Cao, Y., Directed searching digraphs: Monotonicity and complexity, (Proceedings of the 4th International ConferenceTheory and Applications of Models of Computation (TAMC 2007). Proceedings of the 4th International ConferenceTheory and Applications of Models of Computation (TAMC 2007), Lecture Notes in Computer Sci., vol. 4484 (2007), Springer), 136-147 · Zbl 1198.68231
[169] Yang, B.; Dyer, D.; Alspach, B., Sweeping graphs with large clique number, (Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004). Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Comput. Sci., vol. 3341 (2004), Springer), 908-920 · Zbl 1116.05314
[170] Yang, B.; Zhang, R.; Cao, Y., Searching cycle-disjoint graphs, (Proceedings of the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007). Proceedings of the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007), Lecture Notes in Computer Sci., vol. 4616 (2007), Springer), 32-43 · Zbl 1175.68305
[171] Yen, W. C.K.; Tang, C. Y., The searchlight guarding problem on weighted split graphs and weighted cographs, Networks, 35, 195-206 (2000) · Zbl 0963.90067
[172] Zelenevskaya, A. B.; Petrov, N. N., Search problems in graphs with retaliation, Vestnik St. Petersburg Univ. Math., 37, 18-25 (2004) · Zbl 1119.91022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.