<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] or [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”

Settings - Models, Notation, ..

Transformations (Expansions)

Parameters for Temporal Graphs

Classes of Temporal Graphs


AI and Temporal (Neural) Networks

</aside>

Introduction

(Computational) Problem


Temporal Graph Settings

Parameters for Temporal Graphs

Centrality Metrics

Diameter


Reachability

Temporal Paths/Trips/Journeys

Shortest Paths

Multi-Agent Path Finding (MAPF)

Temporal Connected Components

Flows and Cuts

Temporal Separators

Temporal Spanners


Realization - Temporalization

Graph Modification: Shift, Merge, Delete

Network design

Generating Temporal Graphs


Spreading Processes

Exploration

Gossip Theory


Temporal Cliques

Temporal Matching

Feedback Edge Sets

Coloring

Vertex/Edge Cover

Temporal Dominating Set


Search


Games on TG

Temporal Firefighter

Page Status


in progress

in progress

not started

not started (into centrality metrics?)


in progress (add algorithms for reachability graph)

in progress (add literature)

not started (into temporal paths/trips/journeys?)

done for now

done for now

in progress (add literature)

in progress (finish result overview)

done for now


in progress (add literature)

not started

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?)


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

Temporal Problems and their Computational Complexity