An Introduction to Temporal Graphs: An Algorithmic Perspective*

DOI10.1080/15427951.2016.1177801zbMath1461.68161OpenAlexW2950969150MaRDI QIDQ5856438

Othon Michail

Publication date: 26 March 2021

Published in: Internet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/15427951.2016.1177801

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (54)

Edge-Disjoint Branchings in Temporal Graphs ⋮ On exploring always-connected temporal graphs of small pathwidth ⋮ Mengerian temporal graphs revisited ⋮ On computing Pareto optimal paths in weighted time-dependent networks ⋮ The network-untangling problem: from interactions to activity timelines ⋮ On temporal graph exploration ⋮ A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Temporal interval cliques and independent sets ⋮ Non-strict Temporal Exploration ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ Expansion and flooding in dynamic random networks with node churn ⋮ Mengerian graphs: characterization and recognition ⋮ A study of connectivity on dynamic graphs: computing persistent connected components ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Blackout-tolerant temporal spanners ⋮ The complexity of growing a graph ⋮ Blackout-tolerant temporal spanners ⋮ Small Point-Sets Supporting Graph Stories ⋮ Small point-sets supporting graph stories ⋮ Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Eulerian walks in temporal graphs ⋮ Thirty years of SIROCCO a data and graph mining comparative analysis of its temporal evolution ⋮ Unnamed Item ⋮ Using compressed suffix-arrays for a compact representation of temporal-graphs ⋮ EVENT GRAPHS: ADVANCES AND APPLICATIONS OF SECOND-ORDER TIME-UNFOLDED TEMPORAL NETWORK MODELS ⋮ Graph Stories in Small Area ⋮ Graph stories in small area ⋮ Parameterised temporal exploration problems ⋮ Assigning times to minimise reachability in temporal graphs ⋮ A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity ⋮ Finding temporal paths under waiting time constraints ⋮ Temporal network optimization subject to connectivity constraints ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Edge-disjoint branchings in temporal digraphs ⋮ The complexity of routing with collision avoidance ⋮ Coloring temporal graphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Unnamed Item ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ Exploration of dynamic cactuses with sub-logarithmic overhead ⋮ Sliding window temporal graph coloring ⋮ Feedback edge sets in temporal graphs ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs ⋮ The complexity of finding temporal separators under waiting time constraints ⋮ Cluster Editing in Multi-Layer and Temporal Graphs. ⋮ Königsberg sightseeing: Eulerian walks in temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance oracles for time-dependent networks
• Mediated population protocols
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• The labeled perfect matching in bipartite graphs
• Efficient continuous-time dynamic network flow algorithms
• Dynamic graph models
• On the minimum label spanning tree problem
• On the exploration of time-varying networks
• Computation in networks of passively mobile finite-state sensors
• Gossips and telephones
• On temporal graph exploration
• Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata
• Distributed computation in dynamic networks
• Traveling Salesman Problems in Temporal Graphs
• Flooding time in edge-Markovian dynamic graphs
• Coordinated consensus in dynamic networks
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Naming and Counting in Anonymous Unknown Dynamic Networks
• An Introduction to Temporal Graphs: An Algorithmic Perspective
• The Mathematical Coloring Book
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• On Spreading a Rumor
• A survey of gossiping and broadcasting in communication networks
• Some Matching Problems for Bipartite Graphs
• Spanning trees with many or few colors in edge-colored graphs
• Distributed Computing: A Locality-Sensitive Approach
• The Traveling Salesman Problem with Distances One and Two
• Lower Bounds on Information Dissemination in Dynamic Networks
• On the Treewidth of Dynamic Graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Temporal Network Optimization Subject to Connectivity Constraints
• Paths, Trees, and Flowers
• Communication in dynamic radio networks
• A Randomized Rounding Approach to the Traveling Salesman Problem
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• On the Complexity of Information Spreading in Dynamic Networks
• Simple and efficient local codes for distributed stable network construction
• Connectivity and inference problems for temporal networks
• Graph colouring and the probabilistic method

This page was built for publication: An Introduction to Temporal Graphs: An Algorithmic Perspective^*