Interval graphs and seatching

Lefteris M. Kirousis, Christos H. Papadimitriou

Research output: Contribution to journalArticlepeer-review


The interval thickness of a graph G is the minimum clique number over any interval supergraph of G. The node-search number is the least number of searchers required to clear the 'contaminated' edges of a graph. The clearing is accomplished by concurrently having searchers on both of its endpoints. We prove that for any graph, these two parameters coincide.

Original languageEnglish (US)
Pages (from-to)181-184
Number of pages4
JournalDiscrete Mathematics
Issue number2
StatePublished - Jul 1985

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Interval graphs and seatching'. Together they form a unique fingerprint.

Cite this