 |
ΌΝΟΜΑ ΕΡΕΥΝΗΤΗ: Λιάζη Μαρία
ΤΙΤΛΟΣ ΔΙΑΤΡΙΒΗΣ: Προσεγγιστικά Σχήματα, Χρώματα & Πυκνότεροι υπογράφοι
ΕΠΙΣΤΗΜΟΝΙΚΕΣ ΠΕΡΙΟΧΕΣ:
- Αλγοριθμική Επιχειρησιακή Έρευνα
ΣΥΜΒΟΥΛΕΥΤΙΚΗ ΕΠΙΤΡΟΠΗ:
- Επιβλέπων: Ζησιμόπουλος Βασίλειος
- Σύμβουλος: Ηλίας Κουτσουπιάς
- Σύμβουλος: Ιωάννης Μήλης
ΣΥΝΤΟΜΗ ΠΕΡΙΓΡΑΦΗ:
Ερευνάται το πρόβλημα εύρεσης του k-πυκνότερου υπογράφου ενός δοθέντος γράφου (Densest-k-Subgraph: DkS). Το πρόβλημα εύρεσης του k-πυκνότερου υπογράφου έχει ιδιαίτερα χρήσιμες εφαρμογές. Ενδεικτικά αναφέρουμε την εφαρμογή του στο Web γράφο καθώς και στην ασφάλεια παραγωγής στιγμιότυπων τυχαίων δοκιμών. Η έρευνα περιλαμβάνει καταρχάς την ανάπτυξη πολυωνυμικών αλγορίθμων για ειδικές τοπολογίες (δέντρα, γράφοι διαστημάτων, …) και στη συνέχεια την ανάπτυξη προσεγγιστικών αλγορίθμων με εγγυημένη απόδοση για γενικούς γράφους. Παράλληλα, λόγω του ότι το πρόβλημα συνδέεται άμεσα με βασικά θεωρητικά προβλήματα όπως το πρόβλημα της κλίκας (Clique) και το πρόβλημα του χρωματισμού (Coloring), ερευνούνται και οι διάφορες εκδοχές αυτών των προβλημάτων. Επίσης η on-line εκδοχή του προβλήματος είναι βασικός προβληματισμός με στόχο την ανάπτυξη και ανάλυση αλγορίθμων με εγγυημένο λόγο ανταγωνισμού.
|
![]](../images/rdcorner.gif){kind=small}