Lower and upper competitive bounds for online directed graph exploration
From MaRDI portal
Publication:343923
DOI10.1016/j.tcs.2015.11.017zbMath1359.90141OpenAlexW2262759985WikidataQ57310485 ScholiaQ57310485MaRDI QIDQ343923
Klaus-Tycho Foerster, Roger Wattenhofer
Publication date: 29 November 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.11.017
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)
Related Items
An improved lower bound for competitive graph exploration ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ The simple grid polygon exploration problem ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Dispersion of mobile robots on directed anonymous graphs ⋮ Exploring sparse graphs with advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connected graph searching
- Special issue: Selected papers based on the presentations at the 4th workshop on GRAph searching, theory and applications, GRASTA 2011, February 13--18, 2012. Dedicated to Professor Lefteris M. Kirousis on the occasion of his 60th birthday
- An annotated bibliography on guaranteed graph searching
- The vehicle routing problem. Latest advances and new challenges.
- The on-line asymmetric traveling salesman problem
- Tree exploration with advice
- Anonymous graph exploration without collision by mobile robots
- Shortest paths in Euclidean graphs
- Search games
- An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
- Constructing competitive tours from local information
- An explicit lower bound for TSP with distances one and two
- On the nearest neighbor rule for the traveling salesman problem
- The power of a pebble: Exploring and mapping directed graphs
- Online graph exploration: New results on old and new algorithms
- Map construction of unknown graphs by multiple agents
- Graph exploration by a finite automaton
- Exclusive Graph Searching
- Online Graph Exploration with Advice
- Collaborative search on the plane without communication
- Network Exploration by Silent and Oblivious Robots
- The Complexity of Data Aggregation in Directed Networks
- Collective tree exploration
- Treasure Hunt with Advice
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Competitive Online Approximation of the Optimal Search Ratio
- The complexity of searching a graph
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Exploring an unknown graph
- Tree exploration with little memory
- Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology
- Exploring Unknown Environments
- A new approximation algorithm for the asymmetric TSP with triangle inequality
- Solving the ANTS Problem with Asynchronous Finite State Machines
- STACS 2004
- Why Robots Need Maps
- Algorithms – ESA 2005
- How Many Ants Does It Take to Find the Food?
