Abstract
Searching a network for intruders is an interesting and difficult problem. Edge-searching is one such search model, in which intruders may exist anywhere along an edge. Since finding the minimum number of searchers necessary to search a graph is NP–complete, it is natural to look for bounds on the search number. We show lower bounds on the search number using minimum degree, girth, chromatic number, and colouring number.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alspach, B.: Searching and sweeping graphs: A brief survey. Combinatorics 04 (Catania, 2004) Matematiche (Catania) 59, Fasc. I–II, pp. 5–37 (2004)
Bienstock, D., Seymour, P.: Monotonicity in graph searching. Journal of Algorithms 12, 239–245 (1991)
Fellows, M., Langston, M.: On search, decision and the efficiency of polynomial time algorithm. In: 21st ACM Symp. on Theory of Computing, pp. 501–512 (1989)
Frankling, M., Galil, Z., Yung, M.: Eavesdropping games: A graph-theoretic approach to privacy in distributed systems. Journal of ACM 47, 225–243 (2000)
Halin, R.: Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl. Abh. Math. Sem. Univ. Hamburg 31, 156–165 (1967)
Kirousis, L.M., Papadimitriou, C.H.: Searching and pebbling. Theoret. Comput. Sci. 47(2), 205–218 (1986)
LaPaugh, A.S.: Recontamination does not help to search a graph. Journal of ACM 40, 224–245 (1993)
Megiddo, N., Hakimi, S.L., Garey, M., Johnson, D., Papadimitriou, C.H.: The complexity of searching a graph. Journal of ACM 35, 18–44 (1988)
Mycielski, J.: Sur le coloriage des graphes. Coll. Math. 3, 161–162 (1955)
Tusa, Z.: Exponentially many distinguishable cycles in graphs. Graphs, designs and combinatorial geometries (Catania, 1989). J. Combin. Inform. System Sci. 15, 281–285 (1990)
Yang, B., Dyer, D., Alspach, B.: Sweeping graphs with large clique number (extended abstract). In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 880–892. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alspach, B., Dyer, D., Hanson, D., Yang, B. (2007). Lower Bounds on Edge Searching. In: Chen, B., Paterson, M., Zhang, G. (eds) Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE 2007. Lecture Notes in Computer Science, vol 4614. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74450-4_46
Download citation
DOI: https://doi.org/10.1007/978-3-540-74450-4_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74449-8
Online ISBN: 978-3-540-74450-4
eBook Packages: Computer ScienceComputer Science (R0)