Συνεκτικότητα σε χρονικά μεταβαλλόμενα δίκτυα - Αξιώτης, Κυριάκος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2016)
Στα παραδοσιακά γραφήματα, το ελάχιστο πιστοποιητικό συνεκτικότητας ονομάζεται συνδετικό δένδρο. Θεωρούμε μία γενίκευση της έννοιας της συνεκτικότητας για την πιο γενική κλάση των Χρονικά Μεταβαλλόμενων Γραφημάτων με διακριτές χρονικές ετικέτες, όπου το πιστοποιητικό συνεκτικότητας με ελάχιστο μέγεθος ονομάζεται Ελάχιστο Χρονικά Συνεκτικό Υπογράφημα ή Minimum Temporally Connected Subgraph (MTCS). Αρχικά, παρουσιάζουμε διάφορες εφαρμογές οι οποίες μοντελοποιούνται εγγενώς σαν χρονικά μεταβαλλόμενα δίκτυα, καθώς και κάνουμε μια επισκόπηση αποτελεσμάτων στη βιβλιογραφία που σχετίζονται με χρονική συνεκτικότητα, όπως μία γενίκευση του θεωρήματος Menger για χρονικά μεταβαλλόμενα γραφήματα. Στη συνέχεια, παρουσιάζουμε μία νέα κατασκευή, η οποία αποκαθιστά το μέγεθος χειρότερης περίπτωσης ενός ελάχιστου πιστοποιητικού συνεκτικότητας, δείχνοντας ουσιαστικά ότι τα πιστοποιητικά χρονικής συνεκτικότητας μπορεί να είναι ”πολύ πυκνά” ως γραφήματα. Στο τελευταίο μέρος θεωρούμε τα προβλήματα βελτιστοποίησης της εύρεσης ενός πιστοποιητικού χρονικής συνεκτικότητας ελάχιστου κόστους, για δύο παραλλαγές, την single-source (r-MTC) και την all-pairs (MTC). Βρίσκουμε συνδέσεις μεταξύ του r-MTC και του Directed Steiner Tree, κα- θώς και μεταξύ του MTC και του Directed Steiner Forest. Μέσω διάφορων αναγωγών, αποδεικνύουμε τόσο άνω, όσο και κάτω φράγματα στην προσεγγισιμότητα για αυτά τα προβλήματα βελτιστοποίησης. Τέλος, μελετάμε ειδικές κλάσεις γραφημάτων στις οποίες τα παραπάνω προβλήματα έχουν αποδοτικότερους αλγορίθμους. Συγκεκριμένα, αναπτύσσουμε έναν αλγόριθμο πολυωνυμικού χρόνου για το r-MTC όταν το βασικό (underlying) γράφημα έχει φραγμένο δενδροπλάτος, για το MTC όταν το βασικό γράφημα είναι δένδρο, και έναν 2-προσεγγιστικό αλγόριθμο για το MTC όταν το βασικό γράφημα είναι κύκλος. Τα βασικά αποτελέσματα αυτής της εργασίας παρουσιάστηκαν στο διεθνές συνέδριο International Colloquium on Automata, Languages, and Programming (ICALP - Track C) τον Ιούλιο του 2016. [Axio16]