Searching and pebbling

Lefteris M. Kirousis; Christos H. Papadimitriou

doi:10.1016/0304-3975(86)90146-5

Searching and pebbling

Lefteris M. Kirousis, Christos H. Papadimitriou

Computer Science

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

Abstract

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 language	English (US)
Pages (from-to)	205-218
Number of pages	14
Journal	Theoretical Computer Science
Volume	47
Issue number	C
DOIs	https://doi.org/10.1016/0304-3975(86)90146-5
State	Published - 1986

Keywords

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

Access to Document

10.1016/0304-3975(86)90146-5

Cite this

@article{6690bc23b97946f88bedf913be3e6975,

title = "Searching and pebbling",

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

keywords = "Searching a graph, layout parameters of a graph, pebble games, vertex separator of a graph",

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

year = "1986",

doi = "10.1016/0304-3975(86)90146-5",

language = "English (US)",

volume = "47",

pages = "205--218",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - Searching and pebbling

AU - Kirousis, Lefteris M.

AU - Papadimitriou, Christos H.

PY - 1986

Y1 - 1986

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

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

KW - Searching a graph

KW - layout parameters of a graph

KW - pebble games

KW - vertex separator of a graph

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

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

U2 - 10.1016/0304-3975(86)90146-5

DO - 10.1016/0304-3975(86)90146-5

M3 - Article

AN - SCOPUS:0022874903

SN - 0304-3975

VL - 47

SP - 205

EP - 218

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

Searching and pebbling

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this