Συνεκτικότητα Σε Χρονικά Μεταβαλλόμενα Δίκτυα

Abstract

Στα παραδοσιακά γραφήματα, το ελάχιστο πιστοποιητικό συνεκτικότητας ονομάζεται συνδετικόδένδρο. Θεωρούμε μία γενίκευση της έννοιας της συνεκτικότητας για την πιο γενική κλάση των Χρο-νικά Μεταβαλλόμενων Γραφημάτων με διακριτές χρονικές ετικέτες, όπου το πιστοποιητικό συνε-κτικότητας με ελάχιστο μέγεθος ονομάζεται Ελάχιστο Χρονικά Συνεκτικό Υπογράφημα ή MinimumTemporally 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 όταν το βασικόγράφημα είναι κύκλος.Τα βασικά αποτελέσματα αυτής της εργασίας παρουσιάστηκαν στο διεθνές συνέδριο InternationalColloquium on Automata, Languages, and Programming (ICALP - Track C) τον Ιούλιο του 2016.[Axio16]