Loading...
Loading...

Go to the content (press return)

Connected and internal graph searching

Author
Barriere, E.; Fraigniaud, P.; Santoro, N.; Thilikos, D.
Type of activity
Report
Date
2002-07
Code
LSI-02-58-R
Repository
http://hdl.handle.net/2117/97422 Open in new window
URL
http://www.lsi.upc.es/dept/techreps/ps/R02-58.ps.gz Open in new window
Abstract
This paper is concerned with the graph searching game. The search number es(G) of a graph G is the smallest number of searchers required to clear G. A search strategy is monotone (m) if no recontamination ever occurs. It is connected (c) if the set of clear edges always forms a connected subgraph. It is internal (i) if the removal of searchers is not allowed. The difficulty of the ``connected' version and of the ``monotone internal' version of the graph searching problem comes ...
Citation
Barriere, E., Fraigniaud, P., Santoro, N., Thilikos, D. "Connected and internal graph searching". 2002.
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

  • Barriere Figueroa, Eulalia  (author)
  • Fraigniaud, Pierre  (author)
  • Santoro, Nicola  (author)
  • Thilikos Touloupas, Dimitrios  (author)

Attachments