E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης

Αρχική Αναζήτηση

Αποτελέσματα - Λεπτομέρειες

Εντολή Αναζήτησης : Συγγραφέας="Τσαμαρδινός" Και Συγγραφέας="Ιωάννης"

Τρέχουσα Εγγραφή: 7 από 45

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000449964

Τίτλος

Analysis and visualization of hierarchical graphs

Άλλος τίτλος

Ανάλυση και οπτικοποίηση ιεραρχικών γράφων

Συγγραφέας

Κρητικάκης, Γεώργιος

Σύμβουλος διατριβής

Τόλλης, Ιωάννης

Μέλος κριτικής επιτροπής

Πρατικάκης, Πολύβιος
Τσαμαρδινός, Ιωάννης

Περίληψη

Σε αυτό το έργο εξερευνήσαμε αλγορίθμους αιχμής για διάσπαση γράφων σε μονοπάτια και κανάλια. Οι αλγόριθμοι μας είναι γραμμικοί ή σχεδόν γραμμικοί, και τα αποτελέσματα τους είναι πολύ κοντά στο βέλτιστο. Επιπρόσθετα, αναπτύξαμε ένα πλαίσιο οπτικοποίησης ιεραρχικών γραφημάτων που βασίζεται στην διάσπαση σε μονοπάτια και κανάλια και μας βοηθάει να αποκαλύψουμε κρίσιμες πτυχές των ιεραρχιών ενός γράφου. Ακριβέστερα, θα δείξουμε πώς να δημιουργήσουμε μια υποβέλτιστη διάσπαση σε κανάλια ενός άκυκλου κατευθυνόμενου γραφήματος σε σχεδόν γραμμικό χρόνο. Ο αριθμός των καναλιών που δημιουργεί ο αλγόριθμος μας, τα οποία δεν μοιράζονται κοινούς κόμβους, είναι πολύ κοντά στο ελάχιστο. Η χρονική πολυπλοκότητα του αλγορίθμου μας είναι Ο(|E|+c*l), όπου c είναι ο αριθμός των καναλιών και l o αριθμός της μεγαλύτερης διαδρομής του γράφου. Θα δώσουμε αναλυτική εξήγηση στα επόμενα κεφάλαια. Αυτή η θεμελιώδης έννοια έχει ένα ευρύ φάσμα εφαρμογών. Θα επικεντρωθούμε σε μερικές από αυτές. Θα περιγράψουμε εκτενώς πώς να λύσουμε το πρόβλημα της μεταβατικής κλειστότητας και πώς να απαντάμε ερωτήματα σε σταθερό χρόνο δημιουργώντας ένα γνωστό σχήμα από δείκτες. Η μέθοδος μας χρειάζεται O(kc*|Ered|) χρόνο και Ο(kc*|V|) χώρο. Ο όρος kc είναι το μέγεθος μιας υποβέλτιστης διάσπασης καναλιών, ο όρος Ered είναι το σύνολο των μη-μεταβατικών ακμών του γράφου, και ο όρος |V| υποδηλώνει τον αριθμό των κόμβων. Επιπλέον θα δείξουμε πως το |Εred| φράζεται, |Εred|≤width*|V|, και θα περιγράψουμε πως μπορούμε να βρούμε ένα υποσύνολο του Etr (σύνολο μεταβατικών ακμών) χωρίς να υπολογίσουμε τη μεταβατική κλειστότητα. Οι μεθοδολογίες μας συνοδεύονται από εκτενής πειράματα. Τα πειράματα μας δείχνουν ότι οι αλγόριθμοι μας δεν είναι απλώς αποδοτικοί στη θεωρία. Στη πράξη η απόδοση είναι ακόμα ποιο μεγάλη. Ακόμη, έχουμε αναπτύξει το Path-based-Framework (PBF). Το PBF είναι ένα πρόσφατο πλαίσιο οπτικοποίησης ιεραρχικών γραφημάτων που μοιάζει αλλά επίσης διαφέρει από το κλασικό πλαίσιο τεσσάρων φάσεων του Sugiyama. Το PBF βασίζεται στη ιδέα της διάσπασης του γράφου σε κανάλια και μονοπάτια. Επεκτείναμε αυτή την ιδέα. Ζωγραφίζουμε όλες τις ακμές, εφαρμόζουμε επικάλυψη ακμών, ελαχιστοποιούμε το ύψος, και μειώνουμε το πλάτος του γραφήματος εφαρμόζοντας τεχνικές όμοιες με αυτές του χρονο-προγραμματισμού εργασιών. Ως εκ τούτου, παρουσιάζουμε ένα γενικό μοντέλο οπτικοποίησης ιεραρχικών γραφημάτων. Τρέξαμε μια έρευνα χρήστη προκειμένου να μετρήσουμε την ευχρηστία και την αναγνωσιμότητα του. Βάλαμε ερωτήσεις σε γράφους που οπτικοποιήθηκαν από το δικό μας πλαίσιο, και συγκρίναμε την επίδοση των χρηστών σε σχέση με την οπτικοποίηση της βιβλιοθήκης OGDF που χρησιμοποιεί το πλαίσιο του Sygiyama. Τα αποτελέσματα μας φανέρωσαν ένα ξεκάθαρο πλεονέκτημα του PBF σε σχέση με το OGDF σε αυτά τα ερωτήματα.

Φυσική περιγραφή

vi, 53 σ. : σχεδ., πιν., εικ. ; 30 εκ.

Γλώσσα

Αγγλικά

Θέμα

Channel decomposition

Compressed transitive closure

DAG

Data structures

Experimental study

Graph algorithms

Graph hierarchies