Your browser does not support JavaScript!

Αρχική    Συλλογές    Τύπος Εργασίας  

Τύπος Εργασίας

Τεχνικές αναφορές [13] Δημοσιεύσεις [18]
Πτυχιακές εργασίες [1507] Πρακτικά Συνεδρίων
Μεταπτυχιακές εργασίες ειδίκευσης [5933] Μελέτες
Διδακτορικές διατριβές [2282] Προγράμματα Σπουδών
Διάφορα [72]

Τρέχουσα Εγγραφή: 5 από 27

Πίσω στα Αποτελέσματα Προηγούμενη σελίδα
Επόμενη σελίδα
Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 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
Hierarchical graph drawings
Indexing schemes
Path concatenation
Path decomposition
Performance
Query processing
Transitive closure
Transitive reduction
Άκυκλοι γράφοι
Αλγόριθμοι γράφων
Απόδοση
Διάσπαση γράφου σε κανάλια
Διάσπαση γράφου σε μονοπάτια
Διαχείριση ερωτημάτων
Δομές δεδομένων
Ιεραρχίες γράφων
Ιεραρχικά γραφήματα
Μεταβατική αφαίρεση
Πειραματική εργασία
Συμπιεσμένη μεταβατική κλειστότητα
Συνένωση μονοπατιών
Σχήμα δεικτών
Ημερομηνία έκδοσης 2022-03-18
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας
Μόνιμη Σύνδεση https://elocus.lib.uoc.gr//dlib/e/d/f/metadata-dlib-1658299673-108243-810.tkl Bookmark and Share
Εμφανίσεις 904

Ψηφιακά τεκμήρια
No preview available

Κατέβασμα Εγγράφου
Προβολή Εγγράφου
Εμφανίσεις : 6