Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα
Φόρτωση...
Ημερομηνία
Συγγραφείς
Γραμμένος, Φώτιος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Στην παρούσα εργασία, διεξάγουμε μια εμπεριστατωμένη συγκριτική ανάλυση
δύο θεμελιωδών προβλημάτων σε γραφήματα: του εντοπισμού κρίσιμων κόμβων σε
ένα δίκτυο και του υπολογισμού της συνδεσιμότητας κάθε κορυφής. Συγκεκριμένα,
εστιάζουμε στο πρόβλημα της εύρεσης κρίσιμων κόμβων, των οποίων η αφαίρεση
οδηγεί στον μέγιστο δυνατό κατακερματισμό του αρχικού κατευθυνόμενου γραφή ματος. Στόχος μας, είναι να υπολογίσουμε ένα ελάχιστο σύνολο κρίσιμων κόμβων
που, όταν αφαιρούνται, ελαχιστοποιούν μια προκαθορισμένη συνάρτηση συνδεσιμό τητας. Πιο συγκεκριμένα, δεδομένου ενός γραφήματος G και ενός ακέραιου αριθμού
nc, ο στόχος είναι να βρεθεί ένα υποσύνολο S του συνόλου κορυφών V , που περιέ χει το πολύ nc κόμβους, έτσι ώστε η συνάρτηση συνδεσιμότητας f(G \ S) να ελα χιστοποιείται, αντιπροσωπεύοντας έτσι ένα συγκεκριμένο μέτρο κατακερματισμού.
Ειδικότερα, όταν nc = 1, ο στόχος είναι να εντοπιστεί μια κορυφή x στην V τέτοια
ώστε η f(G \ x) να ελαχιστοποιείται, χαρακτηρίζοντας την εν λόγω κορυφή x ως
τον πιο κρίσιμο κόμβο στο G. Παρέχουμε υλοποιήσεις των αξιολογημένων αλγορίθ μων και παρουσιάζουμε μια εκτεταμένη πειραματική μελέτη τόσο σε πραγματικάς
όσο και σε τεχνητάς δεδομένα. Κατά συνέπεια, η παρούσα εργασία αποσκοπεί στη
σύγκριση ταχύτερων αλγορίθμων προσέγγισης και πρακτικών ευρετικών μεθόδων
που λειτουργούν σε σχεδόν γραμμικό χρόνο. Εφαρμόζοντας το άπληστο αλγοριθ μικό πλαίσιο μέχρι να αφαιρεθούν nc κορυφές, αναπτύσσουμε μια αποτελεσματική
ευρετική μέθοδο για τη γενική περίπτωση, η οποία λειτουργεί σε O(nc(m+n)) χρόνο
Περιγραφή
Λέξεις-κλειδιά
Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Γεωργιάδης, Λουκάς
Εξεταστική επιτροπή
Νομικός, Χρήστος
Παπαδόπουλος, Χάρης
Παπαδόπουλος, Χάρης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
81