Searching and pebbling
type: Item
instance of: scholarly article
title: Searching and pebbling
zbMATH Open document ID: 0616.68064
DOI: 10.1016/0304-3975(86)90146-5
author: L. M. Kirousis
author: Christos Papadimitriou
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: For a directed acyclic graph (dag) D the progressive pebble demand number pb(D) is the minimal number of pebbles needed to place a pebble on every vertex of D exactly once, by using the rules: (i) a pebble can be placed on a vertex if all its predecessors are pebbled; (ii) a pebble can be deleted at any time. For an undirected graph \(G=(V,E)\) the progressive node search number pns(G) is the minimal number of pebbles (called guards) needed to clear all edges of G, by using the rules: (i) a guard can be placed on a vertex at any time; (ii) a guard can be deleted at any time; (iii) an edge becomes clear when both its endpoints contain a guard. The node-search number is defined analogously using the additional rule: (iv) a clear edge becomes contaminated (not clear), when there is a path leading from it to a contaminated edge. The vertex separator of G is \(vs(G)=\min_{L} \max_{i}| \{v\in V|\) L(v)\(\leq i\) and \(\exists w\in V:\) \(L(w)>i\) and \(\{\) v,w\(\}\) is an edge\(\}|\) over all bijective vertex numberings (layouts) L:V\(\to \{1,...,| V| \}.\) The following results are proved: a) \(ns(G)=pns(G)\); b) the problem ''ns(G)\(\leq k?''\) is NP-complete; c) \(ns(G)=\min \{pb(D)|\) D is dag and G is the underlying undirected graph of \(D\}\) ; d) \(ns(G)=vs(G)+1\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3999311
zbMATH Keywords: layout parameters of a graph
zbMATH Keywords: games played on graphs
zbMATH Keywords: graph-searching games
zbMATH Keywords: pebble games
zbMATH Keywords: NP-completeness
zbMATH Keywords: directed acyclic graph
zbMATH Keywords: progressive pebble demand number
zbMATH Keywords: undirected graph
zbMATH Keywords: progressive node search number
zbMATH Keywords: node-search number
zbMATH Keywords: vertex separator
reviewed by: Jürgen Ebert
Wikidata QID: Q29030357
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90146-5
OpenAlex ID: W2015469394
cites work: On Time Versus Space
cites work: Recontamination does not help to search a graph
cites work: Black-white pebbles and graph separation
cites work: Flit-serial packet routing on meshes and tori
cites work: Q3326858
cites work: The complexity of searching a graph
cites work: A comparison of two variations of a pebble game on graphs
cites work: Q4159394
cites work: Bandwidth and pebbling
cites work: Complete Register Allocation Problems
description: scientific article; zbMATH DE number 3999311