{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320957"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320957","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Counting complexity: compressed Ηamming distance, vertex covers and recent highlights","abstract":"Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την εργασία δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον τομέα.","abstract_html":"Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ&#x27; αυτήν την εργασία δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον τομέα.","abstract_has_math":false,"creators":["Νέμπαρης Ιωάννης"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:26:35Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320957"],"render_values":[{"text":"uoadl:1320957","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320957","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320957","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1320957","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Νέμπαρης Ιωάννης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320957","https://pergamos.lib.uoa.gr/uoa/dl/object/1320957"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την εργασία δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον τομέα.","In this article, we tackle the compressed Hamming distance problem. The Hamming distance is an easy problem, but when we move to a compressed input (via the SLP compression method) the problem becomes #P-complete. We propose a range of algorithms for specific cases of the problem. Secondly, we deal with the counting vertex covers problems in paths,cycles and trees, and answer more specific questions like the probability of a vertex being part of a cover, and the number of covers for any specific size <n in the graph. Finally we refer to some milestones of the field of the last 30 years."]},{"key":"dc:title","label":"Title","values":["Counting complexity: compressed Ηamming distance, vertex covers and recent highlights"]}]}],"canonical_facts":{"dc:creator":["Νέμπαρης Ιωάννης"],"dc:date":["2015"],"dc:description":["Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την εργασία δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον τομέα.","In this article, we tackle the compressed Hamming distance problem. The Hamming distance is an easy problem, but when we move to a compressed input (via the SLP compression method) the problem becomes #P-complete. We propose a range of algorithms for specific cases of the problem. Secondly, we deal with the counting vertex covers problems in paths,cycles and trees, and answer more specific questions like the probability of a vertex being part of a cover, and the number of covers for any specific size <n in the graph. Finally we refer to some milestones of the field of the last 30 years."],"dc:identifier":["uoadl:1320957","https://pergamos.lib.uoa.gr/uoa/dl/object/1320957"],"dc:language":["English"],"dc:title":["Counting complexity: compressed Ηamming distance, vertex covers and recent highlights"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:35Z"}