ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 10/11/2017   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο:"2-Συνδεσιμότητα σε Κατευθυνόμενα Γραφήματα", Λουκάς Γεωργιάδης

Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος θα πραγματοποιηθεί την Παρασκευή 10/11/2017 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής, ομιλία με τίτλο "2-Συνδεσιμότητα σε Κατευθυνόμενα Γραφήματα". Ομιλητής θα είναι ο κ.Λουκάς Γεωργιάδης, Επίκουρος Καθηγητής του Τμήματος Μηχανικών Η/Υ & Πληροφορικής, Πανεπιστημίου Ιωαννίνων.

ΠΕΡΙΛΗΨΗ

Στο πρόβλημα της 2-συνδεσιμότητας (2-reachability) μας δίνεται ένα κατευθυνόμενο γράφημα G για το οποίο θέλουμε να προσδιορίσουμε εάν υπάρχουν 2 ανεξάρτητα μονοπάτια (χωρίς κοινές ακμές ή κοινούς κόμβους) από ένα κόμβο u προς ένα κόμβο v. Παρουσιάζουμε ένα αλγόριθμο ο οποίος υπολογίζει τη 2-συνδεσιμότητα για όλα τα ζεύγη κόμβων (all-pairs 2-reachability) σε χρόνο Ο(n^ω log⁡n ), όπου n το πλήθος των κόμβων του G και ω ο εκθέτης του πολλαπλασιασμού πινάκων. Επομένως, δείχνουμε ότι ο υπολογισμός της 2-συνδετικότητας γίνεται σχεδόν στον ίδιο χρόνο με τον υπολογισμό της μεταβατικής κλειστότητας (transitive closure) του G. Επιπλέον, αν το G είναι ισχυρά συνεκτικό, τότε ο αλγόριθμος μας τρέχει σε O(n^ω) χρόνο.
Δείχνουμε, επίσης, πως μπορούμε να χρησιμοποιήσουμε τη 2-συνδεσιμότητα για να υπολογίσουμε όλα τα δένδρα κυριαρχίας (dominator trees) του G σε O(n^2) επιπρόσθετο χρόνο. Με τη βοήθεια αυτών των δένδρων μπορούμε να απαντάμε σε σταθερό χρόνο διάφορα ερωτήματα συνδεσιμότητας στο G. Για παράδειγμα, μπορούμε να προσδιορίσουμε σε Ο(1) χρόνο αν για δύο κόμβους u,v και μια ακμή (ή κόμβο) x υπάρχει μονοπάτι από τον u προς τον v που να αποφεύγει την ακμή (ή τον κόμβο) x.

©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA
created by data|SCIENCE

Valid XHTML 1.0 Strict Valid CSS!