National and Kapodistrian University of Athens
Equivalent definitions for Block Elimination Distance and a polynomial kernel
Abstract
dc:descriptionΗ δισυνεκτική απόσταση εξάλειψης είναι μία παράμετρος σε γραφήματα που μετράει την "απόσταση" των δισυνεκτικών συνιστωσών ενός γραφήματος από μία δεδομένη κλάση γραφημάτων. Όταν η υποδεικνούμενη κλάση γραφημάτων είναι η κλάση των γραφημάτων χωρίς ακμές, χρησιμοποιούμε τον όρο δισυνεκτικό δεντροβάθος για να περιγράψουμε την παράμετρο. Στην παρούσα διπλωματική, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος είναι ισοδύναμο με το ελάχιστο πλήθος χρωμάτων ενός χρωματισμού που αποδίδει κορυφή μοναδικού χρώματος σε κάθε δισυνεκτικό υπογράφημα του γραφήματος. Επιπροσθέτως, εισάγουμε μια ειδική περίπτωση ενός μη έγκυρου ακμοχρωματισμού που μπορεί να λειτουργήσει ως ένας εναλλακτικός ορισμός του δισυνεκτικού δεντροβάθους, ο οποίος καλείται κατάταξη ακμών κύκλου. Έπειτα, συνδέουμε το δισυνεκτικό δεντροβάθος με παίγνια αναζήτησης σε γραφήματα, εισάγοντας δύο παραλλαγές του παίγνιου "κλέφτες και αστυνόμοι" οι οποίες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του δισυνεκτικού δεντροβάθους ενός γραφήματος. Τέλος, αποδεικνύουμε ότι το δισυνεκτικό δεντροβάθος επιδέχεται πολυωνυμικό πυρήνα παραμετρικοποιημένο ως προς το μέγεθος του Καλύμματος Κορυφών.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Μαυρόπουλος Φίλιππος
- Mavropoulos Filippos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3245817