Υπολογισμός κρίσιμων κόμβων σε κατευθυνόμενα γραφήματα

Γραμμένος, Φώτιος

Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/38151

Full metadata record

DC Field	Value	Language
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.type	masterThesis	el
heal.type.en	Master thesis	en
heal.type.el	Μεταπτυχιακή εργασία	el
heal.dateAvailable	2024-07-05T11:21:01Z	-
heal.language	el	el
heal.access	free	el
heal.recordProvider	Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής	el
heal.publicationDate	2024-07-03	-
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.advisorName	Γεωργιάδης, Λουκάς	el
heal.committeeMemberName	Νομικός, Χρήστος	el
heal.committeeMemberName	Παπαδόπουλος, Χάρης	el
heal.academicPublisher	Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής	el
heal.academicPublisherID	uoi	el
heal.numberOfPages	81	el
heal.fullTextAvailability	true	-
Appears in Collections:	Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΗΥΠ

Show simple item record

Files in This Item:

File	Description	Size	Format
Computing_critical_nodes_in_Directed_graphs.pdf		905.73 kB	Adobe PDF	View/Open

Show simple item record

Repository of UOI "Olympias"