The cost of monotonicity in distributed graph searching

DOI10.1007/S00446-009-0089-1MaRDI QIDQ2377133zbMATH OpenOpenAlexFDO

Authors David Ilcinkas, Nicolas Nisse, David Soguet

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

competitive ratiograph searchingmobile agentmonotonicity

Mathematics Subject Classification ID

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

Recommendations

• Distributed Chasing of Network Intruders
• Distributed chasing of network intruders
• Graph searching with advice
• Graph Searching with Advice
• Searching for an evader in an unknown graph by an optimal number of searchers

Cites work

• Algorithms and Computation
• An annotated bibliography on guaranteed graph searching
• Connected Treewidth and Connected Graph Searching
• Contiguous search problem in Sierpiński graphs
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Decontamination of hypercubes by mobile agents
• Distributed chasing of network intruders
• Graph searching with advice
• scientific article; zbMATH DE number 3650583 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• Monotonicity in graph searching
• Monotony properties of connected visible graph searching
• Recontamination does not help to search a graph
• Searching is not jumping.
• The complexity of searching a graph

Cited in

(15)

• Graph searching with advice
• Finding small-width connected path decompositions in polynomial time
• Distributed graph searching with a sense of direction
• A distributed algorithm for computing the node search number in trees
• Throttling processes equivalent to full throttling on trees
• More agents may decrease global work: a case in butterfly decontamination
• Network decontamination with temporal immunity by cellular automata
• 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
• On-line search in two-dimensional environment
• Connected graph searching
• Further results on the hunters and rabbit game through monotonicity
• Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
• Network decontamination under m-immunity
• Distributed chasing of network intruders

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

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