A distributed algorithm for computing the node search number in trees

DOI10.1007/S00453-011-9524-3MaRDI QIDQ2429351zbMATH OpenOpenAlexFDO

Authors David Coudert, Florian Huc, 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

pathwidthdistributed algorithmgraph searchingprocess numberedge search numbernode search number

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Recommendations

• Edge and node searching problems on trees
• scientific article; zbMATH DE number 1222842
• The cost of monotonicity in distributed graph searching
• scientific article; zbMATH DE number 4058884
• Distributed algorithms for depth-first search

Cites work

• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• scientific article; zbMATH DE number 4202053 (Why is no real title available?)
• An annotated bibliography on guaranteed graph searching
• Characterization of graphs and digraphs with small process numbers
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Edge and node searching problems on trees
• Graph minors. I. Excluding a forest
• Nondeterministic graph searching: from pathwidth to treewidth
• Pathwidth is NP-Hard for Weighted Trees
• Recontamination does not help to search a graph
• Searching and pebbling
• Searching is not jumping.
• The complexity of searching a graph
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width

Cited in

(6)

• Non-deterministic graph searching in trees
• Distributed tree comparison with nodes of limited memory
• Distributed search trees: fault tolerance in an asynchronous environment
• On the monotonicity of process number
• Tradeoffs in process strategy games with application in the WDM reconfiguration problem
• Exclusive graph searching vs. pathwidth

This page was built for publication: A distributed algorithm for computing the node search number in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429351)