<aside> <img src="/icons/exclamation-mark_orange.svg" alt="/icons/exclamation-mark_orange.svg" width="40px" />

A collection of problems analysed for temporal graphs with state of the art techniques, results or references.

</aside>

The following is work in progress. If you realize that a paper, a result, a problem, etc is missing or there are any mistakes, feel free to reach out. If you would like to add a summary for one of the topics or contribute in any other way, just write me an email. email: [email protected]

<aside> <img src="/icons/reorder_gray.svg" alt="/icons/reorder_gray.svg" width="40px" />

NAVIGATION


Import Sep 5, 2024

Problems

Different, Related Problems


History and Names of “Temporal Graphs”

Definition of Temporal Graphs

Transformations (Expansions)

Parameters for Temporal Graphs

Classes of Temporal Graphs


AI and Temporal (Neural) Networks

</aside>

Introduction

(Computational) Problem


Parameters for Temporal Graphs


Reachability

Temporal Paths/Trips/Journeys

Shortest Temporal Paths

Multi-Agent Path Finding (MAPF)

Temporal Connected Components

Flows and Cuts

Temporal Separators

Temporal Spanners


Algorithmic Meta-Theorems (FO,MSO)

Temporal Isomorphisms, Equivalence Relations


Network design

Realization - Temporalization

Graph Modification: Shift, Merge, Delete

Generating Temporal Graphs


Spreading Processes

Exploration

Gossip Theory

Reconfigurable Networks


Temporal Cliques

Temporal Matching

Feedback Edge Sets

Coloring

Vertex/Edge Cover

Temporal Dominating Set


Search


Games on TG

Temporal Firefighter


Centrality Metrics

Diameter

Page Status


in progress


in progress (add algorithms for reachability graph)

in progress (decide on structure)

in progress (add computational overview)

done for now

done for now

in progress (add literature)

in progress (finish result overview)

done for now


in progress

not started


not started

in progress (add literature)

not started (merge with pertubation?)

in progress (add theoretical generation functions)


in progress (related to exploration)

in progress (add literature)

in progress (merge with Spreading?)

not started

List of Computational Problems on Temporal Graphs

Collection of Temporal Problems with Results on bounded treewidth footprint (+ lifetime/degree)

Overview of Computational Problems and their Computational/Parameterized/Approximation Complexity