Αποδοτικοί αλγόριθμοι για ορισμένα προβλήματα συνεκτικότητας σε στατικά και δυναμικά γραφήματα

Περίληψη

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

Περίληψη σε άλλη γλώσσα

In this thesis, we provide efficient algorithms for some connectivity problems in undirected graphs, in the static, dynamic, and sensitivity setting. Our contribution can be summarized as follows. (1) We provide the first linear-time algorithms for computing the 4- and 5-edge-connected components in undirected multigraphs. This result answers a theoretical question, and sheds light on the possibility that a linear-time solution may exist for general k. Furthermore, the algorithms that we provide can have a very efficient implementation with the use of elementary data structures. Especially for the case k=5, we provide a novel analysis of the structure of 4-edge cuts in 3-edge-connected graphs, that can guide us into a proper selection of them for our purposes. We believe that this analysis may provide a clue for a general solution for the k-edge-connected components, or other related graph connectivity problems. (2) A key component in our algorithm for the case k=5 is an oracle for ans ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/55974
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/55974
ND
55974
Εναλλακτικός τίτλος
Efficient algorithms for some connectivity problems, in static and dynamic graphs
Συγγραφέας
Κοσίνας, Ευάγγελος (Πατρώνυμο: Ιωάννης)
Ημερομηνία
2024
Ίδρυμα
Πανεπιστήμιο Ιωαννίνων. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Εξεταστική επιτροπή
Γεωργιάδης Λουκάς
Παληός Λεωνίδας
Νομικός Χρήστος
Henzinger Monika
Κοντογιάννης Σπυρίδων
Παπαδόπουλος Χάρης
Παροτσίδης Νικόλαος
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΕπιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική ➨ Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
Φυσικές ΕπιστήμεςΜαθηματικά ➨ Μαθηματικά, γενικά
Λέξεις-κλειδιά
Αλγόριθμοι; Δομές δεδομένων; Γραφήματα; Συνεκτικότητα
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
πιν., σχημ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.