National and Kapodistrian University of Athens
Counting complexity: compressed Ηamming distance, vertex covers and recent highlights
Abstract
dc:descriptionΣε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την εργασία δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον τομέα.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Νέμπαρης Ιωάννης
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320957