Αλγόριθμοι και αποτελέσματα NP-πληρότητας για προβλήματα χρωματισμού και επικάλυψης με μονοπάτια σε τέλεια γραφήματα

Abstract

This work focuses on the complexity status of path cover and coloring problems on classes of perfect graphs. In particular, it deals with designing and analyzing graph algorithms for these problems or, for the cases where this is not possible, with providing NP-completeness results. Most of our results have already been published. We next describe the variations of the path cover and coloring problems that we study in this work. […]

Αυτή η εργασία επικεντρώνεται στη μελέτη της πολυπλοκότητας προβλημάτων επικάλυψης με μονοπάτια και χρωματισμού σε κλάσεις τέλειων γραφημάτων. Συγκεκριμένα, ασχολούμαστε με την σχεδίαση και ανάλυση αλγορίθμων για αυτά τα προβλήματα ή, για τις περιπτώσεις που αυτό δεν είναι δυνατό, δίνουμε αποτελέσματα NP-πληρότητας. Τα περισσότερα αποτελέσματα αυτής της εργασίας έχουν ήδη δημοσιευτεί. Στην συνέχεια περιγράφουμε επεκτάσεις προβλημάτων επικάλυψης και χρωματισμού που μας απασχολούν στη συγκεκριμένη εργασία. […]