Temporal graphs

Abstract

This thesis studies Temporal Graphs, also called Temporal Networks. More specifically, the project aimed to carry out research on the properties of Temporal Graphs, both in general and in specific classes of the model, as well as examine and develop algorithms for solving problems in temporal graph theory. Temporal graphs are graphs that change -often dramatically- as time progresses, however maintaining a fixed number of vertices. We investigate a range of different temporal graph models depending on the way these changes occur, e.g., in a deterministic or probabilistic fashion, in a discrete-time or continuous-time context, etc. In particular, we examine connectivity matters in a model of temporal graphs where changes happen at random discrete moments in time. Within this framework, we also investigated a model of continuous time and developed algorithms that solve connectivity problems in that model. Furthermore, we study temporal network design issues for the discrete-time model of temporal graphs, both in cases where changes happen deterministically and in cases where changes happen at random discrete-time moments. We also introduce and investigate temporal network flows, where we define the problem of computing a maximum flow in a given temporal network and discuss efficient ways of solving it.

Η παρούσα διατριβή μελετά τα Χρονικά Γραφήματα, που ονομάζονται επίσης Χρονικά Δίκτυα. Πιο συγκεκριμένα, το έργο είχε ως στόχο τη διεξαγωγή έρευνας σχετικά με τις ιδιότητες των Χρονικών Γραφημάτων, τόσο γενικά όσο και σε συγκεκριμένες κλάσεις του μοντέλου, καθώς και την εξέταση και ανάπτυξη αλγορίθμων για την επίλυση προβλημάτων στη θεωρία των χρονικών γραφημάτων. Τα χρονικά γραφήματα είναι γραφήματα που μεταβάλλονται –συχνά δραματικά– καθώς ο χρόνος προχωρά, διατηρώντας ωστόσο σταθερό πλήθος κορυφών. Ερευνούμε μια ποικιλία διαφορετικών μοντέλων χρονικών γραφημάτων, ανάλογα με τον τρόπο που συμβαίνουν αυτές οι αλλαγές, π.χ. με ντετερμινιστικό ή πιθανοκρατικό τρόπο, σε διακριτό ή συνεχή χρόνο κ.λπ. Ειδικότερα, εξετάζουμε ζητήματα συνδεσιμότητας σε ένα μοντέλο χρονικών γραφημάτων όπου οι αλλαγές συμβαίνουν τυχαία σε διακριτές χρονικές στιγμές. Στο πλαίσιο αυτό, μελετούμε επίσης ένα μοντέλο συνεχούς χρόνου και αναπτύσσουμε αλγορίθμους που επιλύουν προβλήματα συνδεσιμότητας σε αυτό το μοντέλο. Επιπλέον, μελετούμε ζητήματα σχεδιασμού χρονικών δικτύων για το μοντέλο διακριτού χρόνου, τόσο σε περιπτώσεις όπου οι αλλαγές συμβαίνουν ντετερμινιστικά όσο και σε περιπτώσεις όπου οι αλλαγές συμβαίνουν τυχαία σε διακριτές χρονικές στιγμές. Παρουσιάζουμε επίσης και διερευνούμε τις ροές σε χρονικά δίκτυα, όπου ορίζουμε το πρόβλημα του υπολογισμού της μέγιστης ροής σε ένα δεδομένο χρονικό δίκτυο και συζητούμε αποδοτικούς τρόπους επίλυσής του.