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?
