On temporal graph exploration

DOI10.1016/j.jcss.2021.01.005zbMath1477.68222arXiv1504.07976OpenAlexW2949263370MaRDI QIDQ2662667

Yanyan Li

Publication date: 14 April 2021

Published in: Journal of Computer and System Sciences, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsdistributed algorithminapproximabilitynon-approximabilitybounded treewidthgossiping problemrandom edgesregularly present edgesirregularly present edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (47)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ On exploring always-connected temporal graphs of small pathwidth ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Exploring a dynamic ring without landmark ⋮ On temporal graph exploration ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Distributed exploration of dynamic rings ⋮ Partial sorting problem on evolving data ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Non-strict Temporal Exploration ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ Temporal flows in temporal networks ⋮ How fast can we reach a target vertex in stochastic temporal graphs? ⋮ Cops \& robber on periodic temporal graphs: characterization and improved bounds ⋮ Disentangling the computational complexity of network untangling ⋮ Untangling temporal graphs of bounded degree ⋮ Computing maximum matchings in temporal graphs ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Eulerian walks in temporal graphs ⋮ Unnamed Item ⋮ Temporal matching on geometric graph data ⋮ Parameterised temporal exploration problems ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Temporal Vertex Cover with a Sliding Time Window ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Coloring temporal graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Temporal vertex cover with a sliding time window ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring ⋮ Exploration of dynamic cactuses with sub-logarithmic overhead ⋮ Sliding window temporal graph coloring ⋮ Temporal cliques admit sparse spanners ⋮ The temporal explorer who returns to the base ⋮ Edge exploration of temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ Edge exploration of temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ How fast can we reach a target vertex in stochastic temporal graphs ⋮ Finding colorful paths in temporal graphs ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ Königsberg sightseeing: Eulerian walks in temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traveling salesman problems in temporal graphs
• Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring
• The critical probability of bond percolation on the square lattice equals 1/2
• Largest random component of a k-cube
• Treewidth. Computations and approximations
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Online and offline algorithms for the time-dependent TSP with time zones
• On temporal graph exploration
• On the fault tolerance of the butterfly
• Traveling Salesman Problems in Temporal Graphs
• An Introduction to Temporal Graphs: An Algorithmic Perspective
• Exploration of Periodically Varying Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Cover time and mixing time of random walks on dynamic graphs
• Fast gossiping by short messages
• Measuring Temporal Lags in Delay-Tolerant Networks
• Temporal Network Optimization Subject to Connectivity Constraints
• Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks

This page was built for publication: On temporal graph exploration