{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3245817"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3245817","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Equivalent definitions for Block Elimination Distance and a polynomial kernel","abstract":"Η δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την \"απόσταση\" των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου \"κλέφτες και αστυνόμοι\" οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.","abstract_html":"Η δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την &quot;απόσταση&quot; των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου &quot;κλέφτες και αστυνόμοι&quot; οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.","abstract_has_math":false,"creators":["Μαυρόπουλος Φίλιππος","Mavropoulos Filippos"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-11-19T06:20:13Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3245817"],"render_values":[{"text":"uoadl:3245817","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3245817","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3245817","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%3A3245817","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Μαυρόπουλος Φίλιππος","Mavropoulos Filippos"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"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:3245817","https://pergamos.lib.uoa.gr/uoa/dl/object/3245817"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την \"απόσταση\" των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου \"κλέφτες και αστυνόμοι\" οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.","Block elimination distance is a parameter on graphs that measures the distance of the biconnected components of a graph from a given class of graphs. When the indicated graph class is the class of edgeless graphs, we call the parameter block treedepth. In this thesis, we prove that block treedepth is equivalent to the minimum number of colors needed to color a graph such that every biconnected subgraph has a vertex of unique color. Additionally, we introduce a special kind of non-proper edge coloring that can serve as an alternative for block treedepth, called cycle edge ranking. Moreover, we make a connection between block treedepth and graph searching games by introducing two versions of the cops and robbers game that can be used to calculate the block treedepth of a graph. Finally, we prove that block treedepth has a polynomial kernel when parameterized by the vertex cover number."]},{"key":"dc:title","label":"Title","values":["Equivalent definitions for Block Elimination Distance and a polynomial kernel"]}]}],"canonical_facts":{"dc:creator":["Μαυρόπουλος Φίλιππος","Mavropoulos Filippos"],"dc:date":["2022"],"dc:description":["Η δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την \"απόσταση\" των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου \"κλέφτες και αστυνόμοι\" οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.","Block elimination distance is a parameter on graphs that measures the distance of the biconnected components of a graph from a given class of graphs. When the indicated graph class is the class of edgeless graphs, we call the parameter block treedepth. In this thesis, we prove that block treedepth is equivalent to the minimum number of colors needed to color a graph such that every biconnected subgraph has a vertex of unique color. Additionally, we introduce a special kind of non-proper edge coloring that can serve as an alternative for block treedepth, called cycle edge ranking. Moreover, we make a connection between block treedepth and graph searching games by introducing two versions of the cops and robbers game that can be used to calculate the block treedepth of a graph. Finally, we prove that block treedepth has a polynomial kernel when parameterized by the vertex cover number."],"dc:identifier":["uoadl:3245817","https://pergamos.lib.uoa.gr/uoa/dl/object/3245817"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Equivalent definitions for Block Elimination Distance and a polynomial kernel"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T06:20:13Z"}