Faster exploration of degree-bounded temporal graphs

DOI10.4230/LIPICS.MFCS.2018.36MaRDI QIDQ5005137zbMATH OpenFDO

Authors Thomas Erlebach, Jakob T. Spooner

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2018.36

zbMATH Keywords

algorithmic graph theoryNP-complete problemtemporal graph exploration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The temporal explorer who returns to the base
• The temporal explorer who returns to the base
• Edge exploration of temporal graphs

Cites work

• An introduction to temporal graphs: an algorithmic perspective
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• Online and offline algorithms for the time-dependent TSP with time zones
• Temporal network optimization subject to connectivity constraints
• Traveling salesman problems in temporal graphs

Cited in

(27)

• The complexity of finding small separators in temporal graphs
• Temporal vertex cover with a sliding time window
• Exploration of dynamic cactuses with sub-logarithmic overhead
• Königsberg sightseeing: Eulerian walks in temporal graphs
• Exploration of dynamic networks: tight bounds on the number of agents
• Optimizing reachability sets in temporal graphs by delaying
• Eulerian walks in temporal graphs
• Parameterised temporal exploration problems
• Fast and Simple Connectivity in Graph Timelines
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Two moves per time step make a difference
• Non-strict Temporal Exploration
• Exploration of \(k\)-edge-deficient temporal graphs
• The temporal explorer who returns to the base
• Exploration of k-edge-deficient temporal graphs
• The temporal explorer who returns to the base
• Shortest Journeys in Directed Temporal Graphs
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• Multistage \(s-t\) path: confronting similarity with dissimilarity
• Cops \& robber on periodic temporal graphs: characterization and improved bounds
• Temporal reachability minimization: delaying vs. deleting
• The complexity of computing optimum labelings for temporal connectivity
• Cops \& Robber on periodic temporal graphs
• Kernelizing temporal exploration problems
• Collision-free robot scheduling
• COP numbers of periodic graphs
• When is string reconstruction using de Bruijn graphs hard?

This page was built for publication: Faster exploration of degree-bounded temporal graphs

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