DMVP: Foremost Waypoint Coverage of Time-Varying Graphs

DOI10.1007/978-3-319-12340-0_3zbMATH Open1417.68048arXiv1407.7279OpenAlexW1672217606MaRDI QIDQ2945178FDOQ2945178

Authors: Eric Aaron, Elliot Meyerson, D. Krizanc 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents' navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy $mathcalRsupsetmathcalBsupsetmathcalP$ of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in $mathcalR$, limited approximability in $mathcalB$, and tractability in $mathcalP$. We also give topologies in which DMVP in $mathcalR$ is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

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

Recommendations

• Waypoint routing on bounded treewidth graphs
• Point-to-point shortest paths on dynamic time-dependent road networks
• scientific article; zbMATH DE number 6913891
• Maximizing the coverage of roadmap graph for optimal motion planning
• An A* algorithm framework for the point-to-point time-dependent shortest path problem
• Dynamic approximate vertex cover and maximum matching
• A fully dynamic approximation scheme for shortest paths in planar graphs
• Dynamic graph generation for the shortest path problem in time expanded networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Agent technology and artificial intelligence (68T42)

Cited In (16)

• How fast can we reach a target vertex in stochastic temporal graphs?
• On the expressivity of time-varying graphs
• Computing parameters of sequence-based dynamic graphs
• Deleting edges to restrict the size of an epidemic in temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Temporal vertex cover with a sliding time window
• Temporal vertex cover with a sliding time window
• On short fastest paths in temporal graphs
• Sliding window temporal graph coloring
• How fast can we reach a target vertex in stochastic temporal graphs?
• Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring
• Exploration of dynamic cactuses with sub-logarithmic overhead
• Coloring temporal graphs
• An introduction to temporal graphs: an algorithmic perspective
• An introduction to temporal graphs: an algorithmic perspective
• The temporal explorer who returns to the base

This page was built for publication: DMVP: Foremost Waypoint Coverage of Time-Varying Graphs

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