License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.2
URN: urn:nbn:de:0030-drops-159446
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15944/
Spirakis, Paul G.
Algorithmic Problems on Temporal Graphs (Invited Talk)
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.
BibTeX - Entry
@InProceedings{spirakis:LIPIcs.SAND.2022.2,
author = {Spirakis, Paul G.},
title = {{Algorithmic Problems on Temporal Graphs}},
booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-224-2},
ISSN = {1868-8969},
year = {2022},
volume = {221},
editor = {Aspnes, James and Michail, Othon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15944},
URN = {urn:nbn:de:0030-drops-159446},
doi = {10.4230/LIPIcs.SAND.2022.2},
annote = {Keywords: Temporal graph, stochastic temporal graph, vertex cover, temporal transitivity}
}
|
Keywords: |
|
Temporal graph, stochastic temporal graph, vertex cover, temporal transitivity |
|
Collection: |
|
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
29.04.2022 |
