Low-high orders of directed graphs
| dc.contributor.author | Καρανάσιου, Αικατερίνη | el |
| dc.date.accessioned | 2017-01-27T09:07:16Z | |
| dc.date.available | 2017-01-27T09:07:16Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/27801 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.1841 | |
| dc.rights | An error occurred on the license name. | * |
| dc.rights | An error occurred on the license name. | * |
| dc.rights.uri | An error occurred getting the license - uri. | * |
| dc.rights.uri | An error occurred getting the license - uri. | * |
| dc.subject | Συνεκτικότητα | el |
| dc.subject | Κατευθυνόμενα γραφήματα | el |
| dc.subject | Αραιά υπογραφήματα | el |
| dc.subject | Δυναμικοί αλγόριθμοι | el |
| dc.subject | Connectivity | en |
| dc.subject | Directed graph | en |
| dc.subject | Sparse subgraphs | en |
| dc.subject | Dynamic algorithms | en |
| dc.title | Low-high orders of directed graphs | en |
| dc.title | Χαμηλές-υψηλές διατάξεις σε κατευθυνόμενα γραφήματα | el |
| heal.abstract | 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. | en |
| heal.abstract | Τα γραφήµατα είναι µια απο τις πιο θεµελιώδης κατηγορίες δεδοµένων στην επιστήµη των υπολογιστών. Αυτό έχει σαν αποτέλεσµα οι αλγόριθµοι για τον χειρισµό τους, και για τον υπολογισµό σχέσεων σε αυτά, να είναι ιδιαίτερα σηµαντικοί στον κλάδο της πληροφορικής. Μια κατηγορία γραφηµάτων είναι τα συνεκτικά γραφήµατα. Η συνεκτικότητα των γραφηµάτων βρίσκει εφαρµογές σε διάφορους τοµείς όπως για παράδειγµα σε δίκτυα επικοινωνιών, στην θεωρία ηλεκτρικών κυκλωµάτων και σε πλοήγηση δικτύων. Η µελέτη και η ανάλυση ενός γραφήµατος για την -ως προς τις ακµες- και -ως προς τους κόµβους- συνεκτικότητα του αποτελεί ενα σηµαντκό ερευνητικό πεδίο της θεωρίας γραφηµάτων. Σε αυτή τη διπλώµατική ερευνώνται προβλήµατα συνεκτικότητας σε κατευθυνόµενα γρα- φήµατα. ΄Ενα γράφηµα ροής 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 και χρόνο εκτέλεσης γραµµικό. Τέλος, οι αλγόριθµοι που προτείνονται αναλύονται πειραµατικά σε γραφήµατα που προ- κύπτουν απο πραγµατικές εφαρµογές, και παρουσιάζονται τα αποτέλεσµα της πειραµατικής αυτής µελέτης. | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Γεωργιάδης, Λουκάς | el |
| heal.bibliographicCitation | Βιβλιογραφία : σ. 44-48 | el |
| heal.classification | Directed graphs | en |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Νικολόπουλος, Σταύρος | el |
| heal.dateAvailable | 2017-01-27T09:08:16Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | |
| heal.numberOfPages | 48 σ. | |
| heal.publicationDate | 2016 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.secondaryTitle | incremental algorithms and applications | en |
| heal.secondaryTitle | δυναμικοί αλγόριθμοι και εφαρμογές | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΚΑΡΑΝΑΣΙΟΥ ΑΙΚΑΤΕΡΙΝΗ 2016.pdf
- Μέγεθος:
- 1.46 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: