Efficient algorithms for some connectivity problems, in static and dynamic graphs
Authors: Κοσίνας Ευάγγελος 
Published: February 2024

Στην παρούσα διατριβή παρέχουμε αποδοτικούς αλγορίθμους για ορισμένα προβλήματα συνεκτικότητας σε στατικά και δυναμικά γραφήματα. Τα αποτελέσματά μας μπορούν να συνοψιστούν ως εξής. (1) Αρχικά, παρέχουμε αλγορίθμους γραμμικού χρόνου για τον υπολογισμό των 4- και 5-συνεκτικών συνιστωσών σε μη-κατευθυνόμενα πολυγραφήματα. Έτσι απαντούμε ένα θεωρητικό ερώτημα, και ενισχύουμε την υπόθεση ότι ο υπολογισμός των k-συνεκτικών συνιστωσών μπορεί να επιτευχθεί σε γραμμικό χρόνο για οποιοδήποτε k. Ένα σημαντικό χαρακτηριστικό των αλγορίθμων που παρέχουμε είναι ότι μπορούν να υλοποιηθούν αποδοτικά με την χρήση στοιχειωδών δομών δεδομένων. Ειδικά για την περίπτωση k=5, παρέχουμε και μια καινοτόμο ανάλυση των 4-τομών σε 3-συνεκτικά γραφήματα, η οποία μας καθοδηγεί στην κατάλληλη επιλογή μιας συλλογής αυτών προκειμένου να πετύχουμε τον σκοπό μας. Πιστεύουμε ότι αυτή η ανάλυση μπορεί να έχει εφαρμογές και στην γενικότερη εκδοχή του προβλήματος, ή και σε άλλα σχετικά προβλήματα συνεκτικότητας. (2) Μια βασική συνιστώσα του αλγορίθμου για την περίπτωση k=5 είναι μια αποδοτική δομή που απαντά σε ερωτήματα συνεκτικότητας όταν το γράφημα έχει υποστεί απώλειες το πολύ τεσσάρων ακμών. Συγκεκριμένα, η δομή αυτή κατασκευάζεται σε γραμμικό χρόνο, και απαντά ερωτήματα συνεκτικότητας έπειτα από απώλεια τεσσάρων ακμών σε σταθερό χρόνο. Με αυτές τις προδιαγραφές, η δομή που παρέχουμε είναι ουσιαστικά βέλτιστη, και αυτό είναι ένα αποτέλεσμα ανεξάρτητου ενδιαφέροντος. (3) Παρέχουμε μια δομή που απαντά αποδοτικά σε ερωτήματα συνεκτικότητας όταν το γράφημα υφίσταται απώλειες περιορισμένου πλήθους κόμβων. Πιο συγκεκριμένα, η δομή επεξεργάζεται αποδοτικά την πληροφορία ότι ένα σύνολο κόμβων έχει χαθεί, ώστε να μπορεί να απαντά γρήγορα σε ερωτήματα συνεκτικότητας μεταξύ των κόμβων που απομένουν στο γράφημα. Αυτό το πολύ βασικό πρόβλημα συνεκτικότητας έχει απασχολήσει τους ερευνητές εδώ και πάνω από μια δεκαετία, αλλά όλες οι λύσεις που έχουν προταθεί στην βιβλιογραφία είναι αρκετά περίπλοκες και δύσκολο να υλοποιηθούν αποδοτικά στην πράξη. Η δομή που παρέχουμε εμείς συνιστά την πιο απλή λύση που έχει βρεθεί μέχρι σήμερα: η περιγραφή και η ανάλυσή της είναι σχετικά απλή, και η υλοποίησή της βασίζεται σε απλές και γνωστές δομές δεδομένων. Επιπλέον, η λύση μας εμφανίζει από ορισμένες απόψεις και μια θεωρητική βελτίωση σε σχέση με τις προηγούμενες λύσεις. (4) Τέλος, ασχολούμαστε με το πρόβλημα του υπολογισμού των μεγιστικών k-συνεκτικών υπογραφημάτων σε γραφήματα που μεταβάλλονται με προσθήκη κόμβων ή ακμών. Προτείνουμε ένα γενικό πλαίσιο που ανάγει αυτόν τον υπολογισμό στην διατήρηση των k-συνεκτικών συνιστωσών. Ως απτή εφαρμογή αυτού του πλαισίου, παρέχουμε έναν αποδοτικό αλγόριθμο για την διατήρηση των μεγιστικών 3-συνεκτικών υπογραφημάτων, μέσω αναγωγής σε αλγορίθμους και δομές δεδομένων για την διατήρηση των 3-συνεκτικών συνιστωσών. Επιπλέον, παρέχουμε αποδοτικές κατασκευές αραιών υπογραφημάτων που διατηρούν τα μεγιστικά k-συνεκτικά υπογραφήματα του αρχικού γραφήματος. Τέτοιες κατασκευές επιταχύνουν διάφορους υπολογισμούς που αφορούν τα μεγιστικά k-συνεκτικά υπογραφήματα.