Distributed graph searching with a sense of direction

DOI10.1007/S00446-014-0236-1MaRDI QIDQ2355324zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Piotr Borowiecki, Dariusz Dereniowski, Łukasz Kuszner

Publication date 22 July 2015

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00446-014-0236-1

zbMATH Keywords

connected searchingdistributed algorithmfugitive search gamesgraph explorationonline algorithmpathwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)

Recommendations

• Searching for an evader in an unknown graph by an optimal number of searchers
• Connected searching of weighted trees
• Edge searching weighted graphs
• On the Fast Searching Problem
• Three-fast-searchable graphs

Cites work

• An annotated bibliography on guaranteed graph searching
• Approximate search strategies for weighted trees
• Automata, Languages and Programming
• Capturing an Intruder in the Pyramid
• Communication algorithms with advice
• Connected graph searching
• Connected graph searching in chordal graphs
• Connected searching of weighted trees
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Decontamination of hypercubes by mobile agents
• Deterministic rendezvous in graphs
• Distributed chasing of network intruders
• Drawing maps with advice
• From pathwidth to connected pathwidth
• Graph exploration by a finite automaton
• Graph searching with advice
• How to meet asynchronously (almost) everywhere
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Map construction of unknown graphs by multiple agents
• Online computation with advice
• Optimal graph exploration without good maps
• Pathwidth is NP-Hard for Weighted Trees
• Proving Distributed Algorithms for Mobile Agents: Examples of Spanning Tree Computation in Anonymous Networks
• Rendezvous and election of mobile agents: Impact of sense of direction
• Searching and sweeping graphs: a brief survey
• Searching is not jumping.
• Simple agents learn to find their way: an introduction on mapping polygons
• Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
• The complexity of searching a graph
• The cost of monotonicity in distributed graph searching
• Tree exploration with logarithmic memory

Cited in

(5)

• Edge searching weighted graphs
• Efficiently searching a graph by a smell-oriented vertex process
• Finding small-width connected path decompositions in polynomial time
• On-line search in two-dimensional environment
• Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers

This page was built for publication: Distributed graph searching with a sense of direction

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