Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- Institutes outside Greece
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Akrida, Eleni
- Ακρίδα, Ελένη
Subjects
dc:subject × 21- Γραφήματα
- Χρονικά γραφήματα
- Τυχαία γραφήματα
- Δυσκολία προσεγγιστικής επίλυσης
- Πολυωνυμικοί και προσεγγιστικοί αλγόριθμοι
- NP-hardness
- Graphs
- Temporal Graphs
- Random graphs
- APX hardness
- Polynomial and approximation algorithms
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Μαθηματικά
- Διακριτά μαθηματικά και Συνδυαστική
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
- Mathematics
- Discrete Mathematics and Combinatorics
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/59747