Low-high orders of directed graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Καρανάσιου, Αικατερίνη
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
incremental algorithms and applications
δυναμικοί αλγόριθμοι και εφαρμογές
δυναμικοί αλγόριθμοι και εφαρμογές
Περιγραφή
A number of diverse natural or man-made systems are modeled as graphs, capturing
both the structure and the dynamics of the underlying system. Examples include but are
not limited to the world-wide web, transportation, communication and social networks,
databases, biological systems, circuits, and the control-flow of computer programs. For
this reason, graphs play an important role in many academic disciplines, including mathematics,
computer science, and social sciences. Connectivity problems hold central role in
the area of graph theory and graph algorithms, with numerous practical applications such
as routing, navigation and reliable communication.
In this thesis we deal with problems related to connectivity in directed graphs. A
flow graph G = (V;E; s) is 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 all paths 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 delta of D that certifies
the correctness of D, and has further applications in connectivity and path-determination
problems.
In the first part of the thesis, we consider how to maintain efficiently a low-high order
of a flow graph incrementally under edge insertions. We present two algorithms that run
in O(mn) total time for a sequence of m edge insertions in an initially empty flow graph
with n vertices. Moreover, we provide applications of this result to other incremental
problems in directed graphs.
In the second part of the thesis, we apply low-high orders to a type of network design
problems. Given a directed graph G = (V;E), our goal is to compute the smallest
spanning subgraph of G that maintains the 2-vertex-connectivity relations in G. First, we deal the case where G is 2-vertex-connected and we wish to compute the smallest 2-vertexconnected
spanning subgraph of G. We provide provide a linear-time algorithm that
computes a 2-approximation for this problem, improving significantly the best previous
approximation ratio achievable in linear time which was 3. Then we deal with the more
general case, where G is not 2-vertex-connected, and provide linear-time 6-approximation
algorithms.
We complement our theoretical study of the above problems with an extensive empirical
evaluation of our algorithms, using large real-world graphs taken from a variety
of application areas. The experimental results show that our algorithms are not only
theoretically-efficient but also perform very well in practice.
Τα γραφήµατα είναι µια απο τις πιο θεµελιώδης κατηγορίες δεδοµένων στην επιστήµη των υπολογιστών. Αυτό έχει σαν αποτέλεσµα οι αλγόριθµοι για τον χειρισµό τους, και για τον υπολογισµό σχέσεων σε αυτά, να είναι ιδιαίτερα σηµαντικοί στον κλάδο της πληροφορικής. Μια κατηγορία γραφηµάτων είναι τα συνεκτικά γραφήµατα. Η συνεκτικότητα των γραφηµάτων βρίσκει εφαρµογές σε διάφορους τοµείς όπως για παράδειγµα σε δίκτυα επικοινωνιών, στην θεωρία ηλεκτρικών κυκλωµάτων και σε πλοήγηση δικτύων. Η µελέτη και η ανάλυση ενός γραφήµατος για την -ως προς τις ακµες- και -ως προς τους κόµβους- συνεκτικότητα του αποτελεί ενα σηµαντκό ερευνητικό πεδίο της θεωρίας γραφηµάτων. Σε αυτή τη διπλώµατική ερευνώνται προβλήµατα συνεκτικότητας σε κατευθυνόµενα γρα- φήµατα. ΄Ενα γράφηµα ροής G = (V, E, s) ειναι ενα κατευθυνοµένο γραφηµα µε εναν διακε- κριµένο κατευθυντήριο κόµβο s. ΄Ενα δέντρο κυριαρχίας D ενός γραφήµατος ροής G είναι ενα δέντρο µε αφετηριακό κόµβο s, τέτοιο ώστε κάθε κόµβος v είναι πρόγονος ενός κόµβου w αν και µόνο αν όλα τα µονοπάτια απο τον κόµβο s στον κόµβο w περιέχουνε τον κόµβο v. Τα δέντρα κυριαρχίας έχουν διάφορες εφαρµογές τόσο στην επιστήµη της πληροφορικής όσο και σε άλλες επιστήµες, όπως για παράδειγµα στην βιολογία. Υψηλή-χαµηλή διάταξη δ ενός γραφήµατος ροής G είναι µια προδιάταξη του δέντρου κυριαρχίας D του G, η οποία απο- τελεί ένα πιστοποιητικό ορθότητας του D και έχει διάφορες εφαρµογές στην συνεκτικότητα κατευθυνόµενων γραφηµάτων. Στο πρώτο µέρος της διπλωµατικής αυτής, ερευνάται η δυναµική ενηµέρωση µιας ψηλής- χαµηλής διάταξης δ ενός γραφήµατος ροής G µετα από µια εισαγωγή ακµής στο γράφηµα. Το αποτέλεσµα που παρουσιάζεται ειναι 2 αλγόριθµοι οι οποίοι επιτυγχάνουν χρόνο εκτέλεσης της τάξεως mn µετά απο m εισαγωγές ακµών σε ένα αρχικά άδειο γράφηµα n κόµβων. Στο δεύτερο µέρος της εργασίας, θεωρείται το πρόβληµα έυρεσης ενός ελάχιστου υπο- γραφήµατος του γραφήµατος G σε δυο περιπτώσεις. Στην πρώτη περίπτωση έχοντας ένα γράφηµα G το οποίο ειναι 2-συνεκτικό ως προς τους κόµβους, παρουσιάζεται ένας αλγόριθ- µος µε λόγο προσέγγισης 2 και γραµµικό χρόνο εκτέλεσης. Στην δεύτερη περίπτωση το γράφηµα G δεν ειναι 2-συνεκτικό ως προς τους κόµβους και απαιτείται το υπογράφηµα να διατηρεί κάποια συγκεκριµενα χαρακτηριστικά συνεκτικότητας. Για την τελευταία περίπτωση παρέχονται αλγορίθµοι µε λόγο προσέγγισης 6 και χρόνο εκτέλεσης γραµµικό. Τέλος, οι αλγόριθµοι που προτείνονται αναλύονται πειραµατικά σε γραφήµατα που προ- κύπτουν απο πραγµατικές εφαρµογές, και παρουσιάζονται τα αποτέλεσµα της πειραµατικής αυτής µελέτης.
Τα γραφήµατα είναι µια απο τις πιο θεµελιώδης κατηγορίες δεδοµένων στην επιστήµη των υπολογιστών. Αυτό έχει σαν αποτέλεσµα οι αλγόριθµοι για τον χειρισµό τους, και για τον υπολογισµό σχέσεων σε αυτά, να είναι ιδιαίτερα σηµαντικοί στον κλάδο της πληροφορικής. Μια κατηγορία γραφηµάτων είναι τα συνεκτικά γραφήµατα. Η συνεκτικότητα των γραφηµάτων βρίσκει εφαρµογές σε διάφορους τοµείς όπως για παράδειγµα σε δίκτυα επικοινωνιών, στην θεωρία ηλεκτρικών κυκλωµάτων και σε πλοήγηση δικτύων. Η µελέτη και η ανάλυση ενός γραφήµατος για την -ως προς τις ακµες- και -ως προς τους κόµβους- συνεκτικότητα του αποτελεί ενα σηµαντκό ερευνητικό πεδίο της θεωρίας γραφηµάτων. Σε αυτή τη διπλώµατική ερευνώνται προβλήµατα συνεκτικότητας σε κατευθυνόµενα γρα- φήµατα. ΄Ενα γράφηµα ροής G = (V, E, s) ειναι ενα κατευθυνοµένο γραφηµα µε εναν διακε- κριµένο κατευθυντήριο κόµβο s. ΄Ενα δέντρο κυριαρχίας D ενός γραφήµατος ροής G είναι ενα δέντρο µε αφετηριακό κόµβο s, τέτοιο ώστε κάθε κόµβος v είναι πρόγονος ενός κόµβου w αν και µόνο αν όλα τα µονοπάτια απο τον κόµβο s στον κόµβο w περιέχουνε τον κόµβο v. Τα δέντρα κυριαρχίας έχουν διάφορες εφαρµογές τόσο στην επιστήµη της πληροφορικής όσο και σε άλλες επιστήµες, όπως για παράδειγµα στην βιολογία. Υψηλή-χαµηλή διάταξη δ ενός γραφήµατος ροής G είναι µια προδιάταξη του δέντρου κυριαρχίας D του G, η οποία απο- τελεί ένα πιστοποιητικό ορθότητας του D και έχει διάφορες εφαρµογές στην συνεκτικότητα κατευθυνόµενων γραφηµάτων. Στο πρώτο µέρος της διπλωµατικής αυτής, ερευνάται η δυναµική ενηµέρωση µιας ψηλής- χαµηλής διάταξης δ ενός γραφήµατος ροής G µετα από µια εισαγωγή ακµής στο γράφηµα. Το αποτέλεσµα που παρουσιάζεται ειναι 2 αλγόριθµοι οι οποίοι επιτυγχάνουν χρόνο εκτέλεσης της τάξεως mn µετά απο m εισαγωγές ακµών σε ένα αρχικά άδειο γράφηµα n κόµβων. Στο δεύτερο µέρος της εργασίας, θεωρείται το πρόβληµα έυρεσης ενός ελάχιστου υπο- γραφήµατος του γραφήµατος G σε δυο περιπτώσεις. Στην πρώτη περίπτωση έχοντας ένα γράφηµα G το οποίο ειναι 2-συνεκτικό ως προς τους κόµβους, παρουσιάζεται ένας αλγόριθ- µος µε λόγο προσέγγισης 2 και γραµµικό χρόνο εκτέλεσης. Στην δεύτερη περίπτωση το γράφηµα G δεν ειναι 2-συνεκτικό ως προς τους κόµβους και απαιτείται το υπογράφηµα να διατηρεί κάποια συγκεκριµενα χαρακτηριστικά συνεκτικότητας. Για την τελευταία περίπτωση παρέχονται αλγορίθµοι µε λόγο προσέγγισης 6 και χρόνο εκτέλεσης γραµµικό. Τέλος, οι αλγόριθµοι που προτείνονται αναλύονται πειραµατικά σε γραφήµατα που προ- κύπτουν απο πραγµατικές εφαρµογές, και παρουσιάζονται τα αποτέλεσµα της πειραµατικής αυτής µελέτης.
Περιγραφή
Λέξεις-κλειδιά
Συνεκτικότητα, Κατευθυνόμενα γραφήματα, Αραιά υπογραφήματα, Δυναμικοί αλγόριθμοι, Connectivity, Directed graph, Sparse subgraphs, Dynamic algorithms
Θεματική κατηγορία
Directed graphs
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Γεωργιάδης, Λουκάς
Εξεταστική επιτροπή
Γεωργιάδης, Λουκάς
Παληός, Λεωνίδας
Νικολόπουλος, Σταύρος
Παληός, Λεωνίδας
Νικολόπουλος, Σταύρος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία : σ. 44-48
Ονόματα συντελεστών
Αριθμός σελίδων
48 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: An error occurred on the license name.