Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2019-11-08
Συγγραφέας:
ΘΕΟΔΩΡΟΥ ΝΙΚΟΛΑΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Βασίλειος Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
The Maximum Rooted Connected Expansion problem
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Το πρόβλημα της μέγιστης ριζικής συνεκτικής επέκτασης
Περίληψη:
Η θεωρία γραφημάτων έχει πολλές εφαρμογές στον σύγχρονο κόσμο. Η μελέτη μας σε
αυτήν συνέπεσε με ένα ενδιαφέρον πρόβλημα που ονομάζεται προανάκληση. Η
προανάκληση αποτελεί ένα πολύτιμο εργαλείο για το στόχο της αποτελεσματικής
πλοήγησης στο διαδύκτιο. Ένα σημαντικό ζήτημα στην προανάκληση είναι η ανταλλαγή
μεταξύ του ποσού των πόρων του δικτύου που χάνονται από την προανάκληση και το
κέρδος του χρόνου. Για παράδειγμα, στον ιστό, τα προγράμματα περιήγησης ενδέχεται
να κατεβάζουν εκ των προτέρων έγγραφα, ενώ ένας διαδικτυακός χρήστης πλοηγείται
στο διαδίκτυο. Δεδομένου ότι ο διαδικτυακός χρήστης ακολουθεί τους υπερσυνδέσμους
με έναν απρόβλεπτο τρόπο, η επιλογή των ιστοσελίδων που πρέπει να προανακλήθουν
πρέπει να υπολογιστεί ηλεκτρονικά. Το ερώτημα είναι τότε να προσδιοριστεί το ελάχιστο
ποσό των πόρων που χρησιμοποιούνται από την προανάκληση, που εξασφαλίζει ότι
όλα τα έγγραφα που έχει πρόσβαση ο διαδικτυακός χρήστης, έχουν προηγουμένως
φορτωθεί στην κρυφή μνήμη. Από την άποψη αυτή, η προανάκληση μπορεί να
διαμορφωθεί ως συνδυαστικό παιχνίδι δύο παικτών.
Με γνώμονα τα παραπάνω οι Λάμπρου και συνεργάτες θεώρησαν το ακόλουθο
πρόβλημα μεγιστοποίησης στο οποίο αναφέρονται ως πρόβλημα Maximum Rooted
Connected Expansion (πρόβλημα της μέγιστης ριζικής συνεκτικής επέκτασης), MRCE
που είναι NP-Hard. Με βάση ένα γράφημα G και έναν κόμβο ρίζας v 0 , θέλουμε να
βρούμε ένα υποσύνολο κορυφών S που να ειναι συνδεδεμένο, να περιέχει το v 0
και να μεγιστοποιείται ο λόγος N [S ]/|S|, όπου το N [S ] δηλώνει την κλειστή γειτονιά
του S , δηλαδή περιέχει όλους τους κόμβους του S και όλους τους κόμβους του
S με τουλάχιστον έναν γείτονα .
Αναλύουμε περαιτέρω την προσέγγισή τους σχετικά με τον τρόπο επίλυσης αυτού του
προβλήματος μέσω ενός προσεγγιστικού αλγόριθμου. Μελετήσαμε άλλα σημαντικά
προβλήματα στη θεωρία των γραφημάτων και τα ειδικά προβλήματά τους για να
κατανοήσουμε τη δομή και τη σχέση μεταξύ όλων αυτών και του MRCE. Ως αποτέλεσμα
αυτής της μελέτης χαρτογραφήσαμε αυτά τα προβλήματα σύμφωνα με τη σύνδεσή τους
και την αλληλεπίδραση μεταξύ τους. Η συνεισφορά μας είναι ένας άπληστος
αλγόριθμος για το MRCE που πιστεύουμε μέσω της πειραματικής μας ανάλυσης θα
μπορούσε ενδεχομένως να οδηγήσει σε ένα καλό προσεγγιστικό αποτέλεσμα.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Προανάκληση, μεγιστη ριζική συνεκτική επέκταση, δέντρο μέγιστου βαθμού φύλλων
Αρ. σελίδων ευρετηρίου:
4
Αρ. βιβλιογραφικών αναφορών:
16
