Online graph exploration on trees, unicyclic graphs and cactus graphs

DOI10.1016/J.IPL.2021.106096MaRDI QIDQ2656355zbMATH OpenOpenAlexFDO

Authors Robin Fritsch

Publication date 11 March 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.06690

zbMATH Keywords

graph explorationnearest neighboron-line algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Online graph exploration algorithms for cycles and trees by multiple searchers
• Online Graph Exploration: New Results on Old and New Algorithms
• Online graph exploration: New results on old and new algorithms
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Lower and upper competitive bounds for online directed graph exploration
• scientific article; zbMATH DE number 437566
• On Traversing Layered Graphs On-Line
• Exploration of constantly connected dynamic graphs based on cactuses
• Online graph exploration with advice
• scientific article; zbMATH DE number 177843

Cites work

• Algorithms – ESA 2005
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Competitive concurrent distributed queuing
• Constructing competitive tours from local information
• Exploring Unknown Environments
• scientific article; zbMATH DE number 48139 (Why is no real title available?)
• On the nearest neighbor rule for the traveling salesman problem
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Online graph exploration with advice
• Online graph exploration: New results on old and new algorithms
• Shortest paths without a map

Cited in

(12)

• Online graph exploration: New results on old and new algorithms
• Exploration of dynamic cactuses with sub-logarithmic overhead
• Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs
• Online graph exploration algorithms for cycles and trees by multiple searchers
• Online Graph Exploration: New Results on Old and New Algorithms
• Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles
• Exploration of constantly connected dynamic graphs based on cactuses
• On-line exploration of rectangular cellular environments with a rectangular hole
• An improved upper bound for the online graph exploration problem on unicyclic graphs
• Exploration of graphs with excluded minors
• On time-travel planning in dynamic graphs
• On-line exploration of an unbounded region with one obstacle

This page was built for publication: Online graph exploration on trees, unicyclic graphs and cactus graphs

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