Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/33130Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Tsokaktsis, Daniel | en |
| dc.contributor.author | Τσοκακτσής, Δανιήλ | el |
| dc.date.accessioned | 2023-10-17T11:18:12Z | - |
| dc.date.available | 2023-10-17T11:18:12Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/33130 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.12886 | - |
| dc.rights | Attribution-NonCommercial-ShareAlike 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/3.0/us/ | * |
| dc.subject | Data structures | en |
| dc.subject | Δομές δεδομένων | el |
| dc.subject | Αlgorithms | en |
| dc.subject | Αλγόριθμοι | el |
| dc.subject | Strong connectivity | en |
| dc.subject | Ισχυρή συνεκτικότητα | el |
| dc.subject | Graphs | en |
| dc.subject | Γραφήματα | el |
| dc.subject | Fault-tolerant | en |
| dc.subject | Ανοχή σφαλμάτων | el |
| dc.title | Data structures for 2-fault-tolerant strong connectivity | en |
| dc.title | Δομές δεδομένων για ισχυρή συνεκτικότητα με ανοχή 2 σφαλμάτων | el |
| dc.type | masterThesis | en |
| heal.type | masterThesis | el |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.dateAvailable | 2023-10-17T11:19:12Z | - |
| heal.language | en | el |
| heal.access | free | el |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής. | el |
| heal.recordProvider | University of Ioannina. School of Engineering. Department of Computer Science and Engineering. | en |
| heal.publicationDate | 2023-10 | - |
| heal.abstract | Οι θεμελιώδεις ιδιότητες της προσβασιμότητας και της ισχυρής συνεκτικότητας έχουν μελετηθεί εκτενώς από τους επιστήμονες τόσο για τα κατευθυνόμενα όσο και για τα μη κατευθυνόμενα γραφήματα. Η ανάγκη και η σπουδαιότητα μελέτης αυτών πηγάζει από το γεγονός πως εμφανίζονται σε πληθώρα θεωρητικών και πρακτικών προβλημάτων. Στην παρούσα μεταπτυχιακή εργασία θα ασχοληθούμε με ερωτήματα ισχυρής συνεκτικότητας κορυφών στο 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 είναι το πλήθος των ακμών. Τέλος παρουσιάζουμε πειραματικά αποτελέσματα που αφορούν την κατασκευή δένδρου διάσπασης χαμηλού ύψους και αξιολογούμε την δομή μας πραγματοποιώντας εκτενείς αναλύσεις σε πραγματικά και τεχνητά γραφήματα. | el |
| heal.abstract | 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. | en |
| heal.advisorName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisher | University of Ioannina. School of Engineering. Department of Computer Science and Engineering. | en |
| heal.academicPublisherID | uoi | el |
| heal.numberOfPages | 72 | el |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΗΥΠ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. Τσοκακτσής Δανιήλ (2023).pdf | 393.33 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
