2008 | OriginalPaper | Buchkapitel
On the Fast Searching Problem
verfasst von : Danny Dyer, Boting Yang, Öznur Yaşar
Erschienen in: Algorithmic Aspects in Information and Management
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
Edge searching is a graph problem that corresponds to cleaning a contaminated graph using the minimum number of searchers. We define
fast searching
as a variant of this widely studied problem. Fast searching corresponds to an internal monotone search in which every edge is traversed exactly once and searchers are not allowed to jump. We present a linear time algorithm to compute the fast search number of trees. We investigate the fast search number of bipartite graphs. We also propose a general cost function for evaluating search strategies that utilizes both edge searching and fast searching.