Interval graphs and seatching

Lefteris M. Kirousis; Christos H. Papadimitriou

doi:10.1016/0012-365X(85)90046-9

Interval graphs and seatching

Lefteris M. Kirousis, Christos H. Papadimitriou

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	181-184
Number of pages	4
Journal	Discrete Mathematics
Volume	55
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(85)90046-9
State	Published - Jul 1985

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(85)90046-9

Cite this

@article{438ebd61e47c42de927dbdfad1c5cc77,

title = "Interval graphs and seatching",

abstract = "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.",

author = "Kirousis, {Lefteris M.} and Papadimitriou, {Christos H.}",

year = "1985",

month = jul,

doi = "10.1016/0012-365X(85)90046-9",

language = "English (US)",

volume = "55",

pages = "181--184",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Interval graphs and seatching

AU - Kirousis, Lefteris M.

AU - Papadimitriou, Christos H.

PY - 1985/7

Y1 - 1985/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0000288138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000288138&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(85)90046-9

DO - 10.1016/0012-365X(85)90046-9

M3 - Article

AN - SCOPUS:0000288138

SN - 0012-365X

VL - 55

SP - 181

EP - 184

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

Interval graphs and seatching

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this