Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα
| dc.contributor.author | Γραμμένος, Φώτιος | el |
| dc.date.accessioned | 2024-07-05T11:20:00Z | |
| dc.date.available | 2024-07-05T11:20:00Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/38151 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.17857 | |
| dc.rights | Default License | |
| dc.subject | Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα | el |
| dc.title | Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα | el |
| dc.type | masterThesis | en |
| heal.abstract | Στην παρούσα εργασία, διεξάγουμε μια εμπεριστατωμένη συγκριτική ανάλυση δύο θεμελιωδών προβλημάτων σε γραφήματα: του εντοπισμού κρίσιμων κόμβων σε ένα δίκτυο και του υπολογισμού της συνδεσιμότητας κάθε κορυφής. Συγκεκριμένα, εστιάζουμε στο πρόβλημα της εύρεσης κρίσιμων κόμβων, των οποίων η αφαίρεση οδηγεί στον μέγιστο δυνατό κατακερματισμό του αρχικού κατευθυνόμενου γραφή ματος. Στόχος μας, είναι να υπολογίσουμε ένα ελάχιστο σύνολο κρίσιμων κόμβων που, όταν αφαιρούνται, ελαχιστοποιούν μια προκαθορισμένη συνάρτηση συνδεσιμό τητας. Πιο συγκεκριμένα, δεδομένου ενός γραφήματος G και ενός ακέραιου αριθμού nc, ο στόχος είναι να βρεθεί ένα υποσύνολο S του συνόλου κορυφών V , που περιέ χει το πολύ nc κόμβους, έτσι ώστε η συνάρτηση συνδεσιμότητας f(G \ S) να ελα χιστοποιείται, αντιπροσωπεύοντας έτσι ένα συγκεκριμένο μέτρο κατακερματισμού. Ειδικότερα, όταν nc = 1, ο στόχος είναι να εντοπιστεί μια κορυφή x στην V τέτοια ώστε η f(G \ x) να ελαχιστοποιείται, χαρακτηρίζοντας την εν λόγω κορυφή x ως τον πιο κρίσιμο κόμβο στο G. Παρέχουμε υλοποιήσεις των αξιολογημένων αλγορίθ μων και παρουσιάζουμε μια εκτεταμένη πειραματική μελέτη τόσο σε πραγματικάς όσο και σε τεχνητάς δεδομένα. Κατά συνέπεια, η παρούσα εργασία αποσκοπεί στη σύγκριση ταχύτερων αλγορίθμων προσέγγισης και πρακτικών ευρετικών μεθόδων που λειτουργούν σε σχεδόν γραμμικό χρόνο. Εφαρμόζοντας το άπληστο αλγοριθ μικό πλαίσιο μέχρι να αφαιρεθούν nc κορυφές, αναπτύσσουμε μια αποτελεσματική ευρετική μέθοδο για τη γενική περίπτωση, η οποία λειτουργεί σε O(nc(m+n)) χρόνο | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | el |
| heal.access | free | el |
| heal.advisorName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Νομικός, Χρήστος | el |
| heal.committeeMemberName | Παπαδόπουλος, Χάρης | el |
| heal.dateAvailable | 2024-07-05T11:21:01Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | el |
| heal.numberOfPages | 81 | el |
| heal.publicationDate | 2024-07-03 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | masterThesis | el |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Computing_critical_nodes_in_Directed_graphs.pdf
- Μέγεθος:
- 905.73 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 3.22 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: