Data structures for 2-fault-tolerant strong connectivity
Φόρτωση...
Ημερομηνία
Συγγραφείς
Tsokaktsis, Daniel
Τσοκακτσής, Δανιήλ
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Οι θεμελιώδεις ιδιότητες της προσβασιμότητας και της ισχυρής συνεκτικότητας
έχουν μελετηθεί εκτενώς από τους επιστήμονες τόσο για τα κατευθυνόμενα όσο
και για τα μη κατευθυνόμενα γραφήματα. Η ανάγκη και η σπουδαιότητα μελέτης αυτών πηγάζει από το γεγονός πως εμφανίζονται σε πληθώρα θεωρητικών και
πρακτικών προβλημάτων.
Στην παρούσα μεταπτυχιακή εργασία θα ασχοληθούμε με ερωτήματα ισχυρής
συνεκτικότητας κορυφών στο fault-tolerant (ή αλλιώς sensitivity) μοντέλο. Στο εν
λόγω μοντέλο πραγματοποιούμε ένα σταθερό πλήθος ενημερώσεων στο αρχικό γράφημα κι έπειτα απαντούμε τα ερωτήματα που μας ενδιαφέρουν. Οι ενημερώσεις
είναι παροδικές και αφορούν διαγραφές κορυφών (ή ακμών) και συνήθως υποθέτουμε ότι το πλήθος τους είναι μικρό. Εμείς θα επικεντρωθούμε στην περίπτωση
όπου έχουμε δύο διαγραφές κορυφών. Συνεπώς, τα ερωτήματα θα είναι της μορφής: “Είναι οι κορυφές x και y ισχυρά συνδεδεμένες στο γράφημα G δίχως τις f1 και f2;”
Προκειμένου κανείς να απαντήσει αποδοτικά ερωτήματα της άνωθεν μορφής θα
πρέπει να κατασκευάσει ιδιαίτερες δομές δεδομένων (oracles) οι οποίες, ιδανικά,
θα απαιτούν γραμμικό χώρο και θα απαντούν τα ερωτήματα σε σταθερό χρόνο.
Μέχρι στιγμής στη βιβλιογραφία, για γενικά κατευθυνόμενα γραφήματα και για
τουλάχιστον δύο σφάλματα οι δομές οι οποίες σχετίζονται με το Fault-Tolerant
μοντέλο και μπορούν να χρησιμοποιηθούν για ερωτήματα ισχυρής συνεκτικότητας
απαιτούν Ω(n^2) χώρο, με συνέπεια η χρήση τους να είναι σχεδόν απαγορευτική για μεγάλα γραφήματα.
Εμείς, δοθέντος ενός γραφήματος G, παρουσιάζουμε μία δομή δεδομένων που
απαιτεί O(nh) χώρο και O(h) χρόνο, όπου h το ύψος του δένδρου διάσπασης (decomposition tree) του G σε ισχυρά συνεκτικά υπογραφήματα. Άμεση απόρροια αυτού είναι η κατασκευή δομών με O(n log n) χώρο και O(log n) χρόνο για γραφήματα
σταθερού treewidth, ενώ O(n√n) χώρο και O(√n) χρόνο για επίπεδα γραφήματα.
Επιπλέον, για γενικά κατευθυνόμενα γραφήματα παρουσιάζουμε μία πιο προσεκτική εκδοχή του δένδρου διάσπασης μέσω της οποίας κατασκευάζουμε μία δομή δεδομένων με O(n√m) χώρο και O(√m) χρόνο, όπου m είναι το πλήθος των ακμών.
Τέλος παρουσιάζουμε πειραματικά αποτελέσματα που αφορούν την κατασκευή
δένδρου διάσπασης χαμηλού ύψους και αξιολογούμε την δομή μας πραγματοποιώντας εκτενείς αναλύσεις σε πραγματικά και τεχνητά γραφήματα.
In this thesis, we study the problem of efficiently answering strong connectivity queries under two vertex or edge failures. Given a directed graph G with n vertices, we provide a data structure with O(nh) space and O(h) query time, where h is the height of a decomposition tree of G into strongly connected subgraphs. This immediately implies data structures with O(n log n) space and O(log n) query time for graphs of constant treewidth and O(n√n) space and O(√n) query time for planar graphs. For general directed graphs, we introduce a refined version of our data structure that achieves O(n√m) space and O(√m) query time, where m is the number of edges. In our experimental study, we first evaluate various methods to construct a decomposition tree with small height h in practice. Then, we provide efficient implementations of our data structures and evaluate their empirical performance by conducting an extensive experimental study on real-world and artificial graphs.
In this thesis, we study the problem of efficiently answering strong connectivity queries under two vertex or edge failures. Given a directed graph G with n vertices, we provide a data structure with O(nh) space and O(h) query time, where h is the height of a decomposition tree of G into strongly connected subgraphs. This immediately implies data structures with O(n log n) space and O(log n) query time for graphs of constant treewidth and O(n√n) space and O(√n) query time for planar graphs. For general directed graphs, we introduce a refined version of our data structure that achieves O(n√m) space and O(√m) query time, where m is the number of edges. In our experimental study, we first evaluate various methods to construct a decomposition tree with small height h in practice. Then, we provide efficient implementations of our data structures and evaluate their empirical performance by conducting an extensive experimental study on real-world and artificial graphs.
Περιγραφή
Λέξεις-κλειδιά
Data structures, Δομές δεδομένων, Αlgorithms, Αλγόριθμοι, Strong connectivity, Ισχυρή συνεκτικότητα, Graphs, Γραφήματα, Fault-tolerant, Ανοχή σφαλμάτων
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
Όνομα επιβλέποντος
Γεωργιάδης, Λουκάς
Εξεταστική επιτροπή
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Παπαδόπουλος, Χάρης
Παληός, Λεωνίδας
Παπαδόπουλος, Χάρης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής.
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
University of Ioannina. School of Engineering. Department of Computer Science and Engineering.
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
72
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-ShareAlike 3.0 United States