2007 | OriginalPaper | Buchkapitel
Lower Bounds on Edge Searching
verfasst von : Brian Alspach, Danny Dyer, Denis Hanson, Boting Yang
Erschienen in: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.