LIPIcs.SAND.2022.2.pdf
- Filesize: 318 kB
- 1 pages
Document
Algorithmic Problems on Temporal Graphs (Invited Talk)
Author
Paul G. Spirakis 
-
Part of:
Volume:
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-04-29
File
Document Identifiers
Author Details
Cite AsGet BibTex
Paul G. Spirakis. Algorithmic Problems on Temporal Graphs (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.2
https://doi.org/10.4230/LIPIcs.SAND.2022.2
Abstract
Research on Temporal Graphs has expanded in the last few years. Most of the results till now, address problems related to the notion of Temporal Paths (and Temporal Connectivity). In this talk, we focus, instead, on problems whose main topic is not on Temporal Paths. In particular, we will discuss Temporal Vertex Covers, the notion of Temporal Transitivity, and also issues and models of stochastic temporal graphs. We believe that several algorithmic graph problems, not directly related to paths, can be raised in the temporal domain. This may motivate new research towards lifting more topics of algorithmic graph theory to the temporal case.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Mathematics of computing → Discrete mathematics
Keywords
- Temporal graph
- stochastic temporal graph
- vertex cover
- temporal transitivity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads