The cost of monotonicity in distributed graph searching

DOI10.1007/s00446-009-0089-1zbMath1267.68311OpenAlexW2046510155MaRDI QIDQ2377133

David Soguet, David Ilcinkas, Nicolas Nisse

Publication date: 28 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-009-0089-1

zbMATH Keywords

monotonicitycompetitive ratiomobile agentgraph searching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (12)

Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ Throttling processes equivalent to full throttling on trees ⋮ Network decontamination under \(m\)-immunity ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ A unified approach for gathering and exclusive searching on rings under weak assumptions ⋮ Connected graph searching ⋮ Network Decontamination with Temporal Immunity by Cellular Automata ⋮ On-line search in two-dimensional environment ⋮ Searching by heterogeneous agents ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Distributed graph searching with a sense of direction

Cites Work

• Unnamed Item
• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• Distributed chasing of network intruders
• Monotony properties of connected visible graph searching
• Graph searching with advice
• Contiguous search problem in Sierpiński graphs
• Decontamination of hypercubes by mobile agents
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Connected Treewidth and Connected Graph Searching
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: The cost of monotonicity in distributed graph searching