Decremental dominators and low-high orders in directed acyclic graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Γιάννης, Κωνσταντίνος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Τα γραφήματα είναι μαθηματικά αντικείμενα που μας βοηθούν στο να μοντελοποιήσουμε πολλά αλγοριθμικά προβλήματα. Ένα γράφημα G = (V, E) αποτελείται από ένα σύνολο κορυφών V και ένα σύνολο ακμών E .Τα γραφήματα είναι μείζονος σημασίας για την επιστήμη των πληροφορικής καθώς χρησιμοποιούνται για την αναπαράσταση της σχέσης μεταξύ των αντικειμένων που μελετάμε. Για παράδειγμα, μέσω των γραφημάτων μπορούμε να μοντελο-ποιήσουμε οδικά δίκτυα, τηλεπικοινωνιακά δίκτυα, κοινωνικά δίκτυα, ηλεκτρικά κυκλώματα κ.α. Η χρησιμότητα των γραφημάτων δεν περιορίζεται μόνο στην επιστήμη των πληροφορικής αλλά επεκτείνεται και σε πολλούς ακόμα επιστημονικούς τομείς όπως για παράδειγμα τη χημεία, τη φυσική, τα μαθηματικά και τη βιολογία. Η κατασκευή νέων αλγορίθμων για την επεξεργασία γραφημάτων αποτελεί μεγάλη πρόκληση. Σε αυτή τη διπλωματική εργασία, ασχολούμαστε με πρακτικούς αλγορίθμους για τη διατήρηση ενός δέντρου κυριαρχίας καθώς και μιας λοω-ηιγη διάταξης για κατευθυνόμενα άκυκλα γραφήματα για μια ακολουθία διαγραφών. Έστω G = (V, E, s) ένα κατευθυνόμενο άκυκλο γράφημα με αφετηριακή κορυφή τον κόμβο s. Το δέντρο κυριαρχίας D του γραφήματος G είναι ένα δέντρο με ρίζα τον κόμβο s, τέτοιο ώστε ένας κόμβος v λέμε ότι κυριαρχεί ενός κόμβου w αν και μόνο αν όλα τα μονοπάτια από τη ρίζα s προς τον κόμβο w περνάνε από τον κόμβο v. Τα δέντρα κυριαρχίας έχουν πολλές και σημαντικές εφαρμογές όπως για παράδειγμα στον έλεγχο κυκλωμάτων, στη βιολογία καθώς και σε διάφορα προβλήματα συνεκτικότητας γραφημάτων. Μια λοω-ηιγη διάταξη του G αποτελεί μια προδιάταξη των κόμβων του δέντρου κυριαρχίας D η οποία αποτελεί ένα πιστοποιητικό ορθότητας για το δέντρο κυριαρχίας D και έχει διάφορες εφαρμογές στη συνεκτικότητα των γραφημάτων. Αρχικά, παρουσιάζουμε μια υλοποίηση ενός πρόσφατου αλγορίθμου [ICALP2017] για την ενημέρωση ενός δέντρου κυριαρχίας ενός κατευθυνόμενου άκυκλου γραφήματος για μια ακολουθία διαγραφών και στη συνέχεια μελετάμε το πως μπορούμε να ενημερώσουμε τη λοω-ηιγη διάταξη του άκυκλου γραφήματος παράλληλα με την ενημέρωση του δέντρου κυριαρχίας.
Τα γραφήματα είναι μαθηματικά αντικείμενα που μας βοηθούν στο να μοντελοποιήσουμε πολλά αλγοριθμικά προβλήματα. Ένα γράφημα G = (V, E) αποτελείται από ένα σύνολο κορυφών V και ένα σύνολο ακμών E .Τα γραφήματα είναι μείζονος σημασίας για την επιστήμη των πληροφορικής καθώς χρησιμοποιούνται για την αναπαράσταση της σχέσης μεταξύ των αντικειμένων που μελετάμε. Για παράδειγμα, μέσω των γραφημάτων μπορούμε να μοντελο-ποιήσουμε οδικά δίκτυα, τηλεπικοινωνιακά δίκτυα, κοινωνικά δίκτυα, ηλεκτρικά κυκλώματα κ.α. Η χρησιμότητα των γραφημάτων δεν περιορίζεται μόνο στην επιστήμη των πληροφορικής αλλά επεκτείνεται και σε πολλούς ακόμα επιστημονικούς τομείς όπως για παράδειγμα τη χημεία, τη φυσική, τα μαθηματικά και τη βιολογία. Η κατασκευή νέων αλγορίθμων για την επεξεργασία γραφημάτων αποτελεί μεγάλη πρόκληση. Σε αυτή τη διπλωματική εργασία, ασχολούμαστε με πρακτικούς αλγορίθμους για τη διατήρηση ενός δέντρου κυριαρχίας καθώς και μιας λοω-ηιγη διάταξης για κατευθυνόμενα άκυκλα γραφήματα για μια ακολουθία διαγραφών. Έστω G = (V, E, s) ένα κατευθυνόμενο άκυκλο γράφημα με αφετηριακή κορυφή τον κόμβο s. Το δέντρο κυριαρχίας D του γραφήματος G είναι ένα δέντρο με ρίζα τον κόμβο s, τέτοιο ώστε ένας κόμβος v λέμε ότι κυριαρχεί ενός κόμβου w αν και μόνο αν όλα τα μονοπάτια από τη ρίζα s προς τον κόμβο w περνάνε από τον κόμβο v. Τα δέντρα κυριαρχίας έχουν πολλές και σημαντικές εφαρμογές όπως για παράδειγμα στον έλεγχο κυκλωμάτων, στη βιολογία καθώς και σε διάφορα προβλήματα συνεκτικότητας γραφημάτων. Μια λοω-ηιγη διάταξη του G αποτελεί μια προδιάταξη των κόμβων του δέντρου κυριαρχίας D η οποία αποτελεί ένα πιστοποιητικό ορθότητας για το δέντρο κυριαρχίας D και έχει διάφορες εφαρμογές στη συνεκτικότητα των γραφημάτων. Αρχικά, παρουσιάζουμε μια υλοποίηση ενός πρόσφατου αλγορίθμου [ICALP2017] για την ενημέρωση ενός δέντρου κυριαρχίας ενός κατευθυνόμενου άκυκλου γραφήματος για μια ακολουθία διαγραφών και στη συνέχεια μελετάμε το πως μπορούμε να ενημερώσουμε τη λοω-ηιγη διάταξη του άκυκλου γραφήματος παράλληλα με την ενημέρωση του δέντρου κυριαρχίας.
Περιγραφή
Λέξεις-κλειδιά
Graphs, DAGs
Θεματική κατηγορία
Graphs
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Γεωργιάδης, Λουκάς
Εξεταστική επιτροπή
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Κοντογιάννης, Σπυρίδων
Παληός, Λεωνίδας
Κοντογιάννης, Σπυρίδων
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 30-33
Ονόματα συντελεστών
Αριθμός σελίδων
37 σ.