Back to search
University of Ioannina
Αλγόριθμοι και αποτελέσματα NP-πληρότητας για προβλήματα χρωματισμού και επικάλυψης με μονοπάτια σε τέλεια γραφήματα
Abstract
dc:descriptionThis 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. […]
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Asdre, Katerina
- Ασδρέ, Αικατερίνη
Subjects
dc:subject × 17- Αλγόριθμοι
- Χρωματισμός
- Επικάλυψη με μονοπάτια
- Πολυπλοκότητα
- Τέλεια γραφήματα
- Κλάσεις γραφημάτων
- Algorithms
- NP-completeness
- Coloring
- Path cover
- Complexity
- Perfect graphs
- Graph classes
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/17553