A distributed algorithm for computing the node search number in trees

DOI10.1007/s00453-011-9524-3zbMath1236.68288MaRDI QIDQ2429351

Florian Huc, David Coudert, Dorian Mazauric

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf

zbMATH Keywords

pathwidth; distributed algorithm; graph searching; process number; edge search number; node search number

Mathematics Subject Classification ID

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

68W15: Distributed algorithms

Related Items

On the monotonicity of process number, Tradeoffs in process strategy games with application in the WDM reconfiguration problem, Exclusive graph searching vs. pathwidth, Non-deterministic graph searching in trees

Cites Work

• Unnamed Item
• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• Nondeterministic graph searching: from pathwidth to treewidth
• Graph minors. I. Excluding a forest
• The vertex separation number of a graph equals its path-width
• The vertex separation and search number of a graph
• Edge and node searching problems on trees
• Searching and pebbling
• Characterization of graphs and digraphs with small process numbers
• The complexity of searching a graph
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Recontamination does not help to search a graph
• Pathwidth is NP-Hard for Weighted Trees
• Graph-Theoretic Concepts in Computer Science