Decremental dominators and low-high orders in directed acyclic graphs
| dc.contributor.author | Γιάννης, Κωνσταντίνος | el |
| dc.date.accessioned | 2019-03-14T06:48:29Z | |
| dc.date.available | 2019-03-14T06:48:29Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/29312 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.3038 | |
| dc.rights | Default License | |
| dc.subject | Graphs | en |
| dc.subject | DAGs | en |
| dc.title | Decremental dominators and low-high orders in directed acyclic graphs | en |
| heal.abstract | Graphs are mathematical objects that model many diverse natural or man-made systems. A graph G = (V;E) consists of a set of vertices V together with a set E of edges. Graphs play an important role in computer science because they can be used to represent essentially any pairwise relationship between objects. For example, graphs can model transportation networks, communication networks, social networks, electronic circuits etc. Graphs are useful not only in computer science but in many academic areas such as chemistry, physics, mathematics and biology. Designing e cient graph algorithms can be a very challenging task. In this thesis, we consider practical algorithms for maintaining the dominator tree and a low-high order of a directed acyclic graph (DAG) under edge deletions. Let G=(V, E, s) be a directed graph with a distinguished start vertex s. The dominator tree D of G is a tree rooted at s, such that a vertex v is an ancestor of a vertex w if and only if every path from s to w include v. The dominator tree is a central tool in program optimization and code generation, and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low high order of G is a preorder of D that certi es the correctness of D and has further applications in connectivity and path-determination problems. First, we provide a carefully engineered version of a recent algorithm [ICALP 2017] for maintaining the dominator tree of a directed acyclic graph through a sequence of edge deletions. Then, we show how how to extend this algorithm so that it also maintains a low-high order of the given DAG. Our algorithms, for both tasks, run in O(mn) total time and O(m+n) space, where n is the number of vertices and m is the number of edges before any deletions. These results trivially extend to the case of reducible graphs. We study the eciency of our algorithms in practice by conducting an extensive experimental study, using real-world graphs, taken from a variety of application areas, and articial graphs. The experimental results show that both algorithms perform very well in practice and are orders of magnitude faster than recomputing from scratch. | en |
| heal.abstract | Τα γραφήματα είναι μαθηματικά αντικείμενα που μας βοηθούν στο να μοντελοποιήσουμε πολλά αλγοριθμικά προβλήματα. Ένα γράφημα G = (V, E) αποτελείται από ένα σύνολο κορυφών V και ένα σύνολο ακμών E .Τα γραφήματα είναι μείζονος σημασίας για την επιστήμη των πληροφορικής καθώς χρησιμοποιούνται για την αναπαράσταση της σχέσης μεταξύ των αντικειμένων που μελετάμε. Για παράδειγμα, μέσω των γραφημάτων μπορούμε να μοντελο-ποιήσουμε οδικά δίκτυα, τηλεπικοινωνιακά δίκτυα, κοινωνικά δίκτυα, ηλεκτρικά κυκλώματα κ.α. Η χρησιμότητα των γραφημάτων δεν περιορίζεται μόνο στην επιστήμη των πληροφορικής αλλά επεκτείνεται και σε πολλούς ακόμα επιστημονικούς τομείς όπως για παράδειγμα τη χημεία, τη φυσική, τα μαθηματικά και τη βιολογία. Η κατασκευή νέων αλγορίθμων για την επεξεργασία γραφημάτων αποτελεί μεγάλη πρόκληση. Σε αυτή τη διπλωματική εργασία, ασχολούμαστε με πρακτικούς αλγορίθμους για τη διατήρηση ενός δέντρου κυριαρχίας καθώς και μιας λοω-ηιγη διάταξης για κατευθυνόμενα άκυκλα γραφήματα για μια ακολουθία διαγραφών. Έστω G = (V, E, s) ένα κατευθυνόμενο άκυκλο γράφημα με αφετηριακή κορυφή τον κόμβο s. Το δέντρο κυριαρχίας D του γραφήματος G είναι ένα δέντρο με ρίζα τον κόμβο s, τέτοιο ώστε ένας κόμβος v λέμε ότι κυριαρχεί ενός κόμβου w αν και μόνο αν όλα τα μονοπάτια από τη ρίζα s προς τον κόμβο w περνάνε από τον κόμβο v. Τα δέντρα κυριαρχίας έχουν πολλές και σημαντικές εφαρμογές όπως για παράδειγμα στον έλεγχο κυκλωμάτων, στη βιολογία καθώς και σε διάφορα προβλήματα συνεκτικότητας γραφημάτων. Μια λοω-ηιγη διάταξη του G αποτελεί μια προδιάταξη των κόμβων του δέντρου κυριαρχίας D η οποία αποτελεί ένα πιστοποιητικό ορθότητας για το δέντρο κυριαρχίας D και έχει διάφορες εφαρμογές στη συνεκτικότητα των γραφημάτων. Αρχικά, παρουσιάζουμε μια υλοποίηση ενός πρόσφατου αλγορίθμου [ICALP2017] για την ενημέρωση ενός δέντρου κυριαρχίας ενός κατευθυνόμενου άκυκλου γραφήματος για μια ακολουθία διαγραφών και στη συνέχεια μελετάμε το πως μπορούμε να ενημερώσουμε τη λοω-ηιγη διάταξη του άκυκλου γραφήματος παράλληλα με την ενημέρωση του δέντρου κυριαρχίας. | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Γεωργιάδης, Λουκάς | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 30-33 | el |
| heal.classification | Graphs | en |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Κοντογιάννης, Σπυρίδων | el |
| heal.dateAvailable | 2019-03-14T06:49:30Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | |
| heal.numberOfPages | 37 σ. | |
| heal.publicationDate | 2018 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΓΙΑΝΝΗΣ ΚΩΝΣΤΑΝΤΙΝΟΣ 2018.pdf
- Μέγεθος:
- 2.42 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: