DMVP: Foremost Waypoint Coverage of Time-Varying Graphs

DOI10.1007/978-3-319-12340-0_3zbMATH Open1417.68048OpenAlexW1672217606MaRDI 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)

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

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)

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.

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

Cited in

(16)

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

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)