Your browser does not support JavaScript!

Αρχική    Υπολογισμός Παραμετρικών ως προς το Μακρύτερο Μονοπάτι st-Προσανατολισμών Γράφων: Αλγόριθμοι και Εφαρμογές  

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

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου uch.csd.msc//2005papamanthou
Τίτλος Υπολογισμός Παραμετρικών ως προς το Μακρύτερο Μονοπάτι st-Προσανατολισμών Γράφων: Αλγόριθμοι και Εφαρμογές
Άλλος τίτλος Computing Longest Path Parameterized st-Orientations of Graphs: Algorithms and Applications
Συγγραφέας Παπαμάνθου, Χαράλαμπος
Περίληψη Το πρόβλημα του προσανατολισμού ενός μη κατευθυνόμενου γράφου έτσι ώστε να έχει μια πηγή (source), μια δεξαμενή (sink) και καθόλου κύκλους (st-προσανατολισμός), είναι πολύ σημαντικό σε πολλούς αλγόριθμους γράφων και εφαρμογές, όπως η σχεδίαση γράφων (ιεραρχική σχεδίαση, αναπαράσταση ορατότητας, ορθογώνια σχεδίαση), ο χρωματισμός γράφων, το πρόβλημα του μακρύτερου μονοπατιού και η δρομολόγηση δικτύων. Οι περισσότεροι αλγόριθμοι χρησιμοποιούν οποιονδήποτε αλγόριθμο που παράγει έναν τέτοιο προσανατολισμό χωρίς να απαιτούν κάποιες συγκεκριμένες ιδιότητες του προσανατολισμένου γράφου. Σε αυτήν την εργασία παρουσιάζεται ένας καινούριος αλγόριθμος που υπολογίζει st-προσανατολισμούς γράφων συγκεκριμένων χαρακτηριστικών. Συγκεκριμένα, περιγράφουμε νέους αλγορίθμους με θεωρητικά και πειραματικά αποτελέσματα που δείχνουν ότι υπάρχει ένας αποδοτικός τρόπος να ελέγξουμε το μήκος του μακρύτερου μονοπατιού που αντιστοιχεί σε κάποιον st-προσανατολισμό. Η σημαντικότητα αυτής της ερευνητικής κατεύθυνσης είχε τονισθεί στο παρελθόν, ειδικότερα στο χώρο της σχεδίασης γράφων. Οι αλγόριθμοι που παρουσιάζονται υπολογίζουν st -προσανατολισμένους γράφους με μήκος μακρύτερου μονοπατιού που μπορεί να καθοριστεί από παραμέτρους. Το μήκος αυτό είναι πολύ σημαντικό στην ποιότητα των λύσεων που παράγονται από διάφορους αλγορίθμους. Για παράδειγμα, τα όρια εμβαδού πολλών αλγορίθμων σχεδίασης γράφων εξαρτώνται από το μήκος του μακρύτερου μονοπατιού του st-προσανατολισμένου γράφου. Επιπλέον, συγκεκριμένοι st-προσανατολισμοί γράφων μπορούν να προσεγγίσουν καταλλήλως μορφοποιημένα προβλήματα γράφων (μακρύτερο μονοπάτι, χρωματισμός γράφων). Τέλος, η δρομολόγηση δικτύων μέσω st-αριθμήσεων δίνει πολλαπλά μονοπάτια προς κάποιο κόμβο και συνεπώς ο υπολογισμός διαφορετικών (παραμετρικών ως προς το μακρύτερο μονοπάτι) st-αριθμήσεων παρέχει ελαστικότητα σε πολλά υπάρχοντα πρωτόκολλα δρομολόγησης δικτύων. Εξετάζουμε τις περισσότερες από αυτές τις εφαρμογές και δείχνουμε ότι υπάρχει πραγματικά η ανάγκη συστηματικού υπολογισμού παραμετρικών st-προσανατολισμών.
Ημερομηνία έκδοσης 2005-07-01
Ημερομηνία διάθεσης 2005-07-20
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 114

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

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