Searching and pebbling

Lefteris M. Kirousis, Christos H. Papadimitriou

Research output: Contribution to journalArticlepeer-review


We relate the search number of an undirected graph G with the minimum and maximum of the progressive pebble demands of the directed acyclic graphs obtained by orienting G. Towards this end, we introduce node-searching, a slight variant of searching, in which an edge is cleared by placing searchers on both of its endpoints. We also show that the minimum number of searchers necessary to node-search a graph equals its vertex separator plus one.

Original languageEnglish (US)
Pages (from-to)205-218
Number of pages14
JournalTheoretical Computer Science
Issue numberC
StatePublished - 1986


  • Searching a graph
  • layout parameters of a graph
  • pebble games
  • vertex separator of a graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Searching and pebbling'. Together they form a unique fingerprint.

Cite this