University of Ioannina
Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών
Abstract
dc:descriptionIn this work we provide characterizations of two new classes of perfect graphs, namely colinear and linear graphs. Moreover, we present polynomial-time algorithms or NP-completeness results for various types of the coloring problem on graphs and polynomial-time algorithms for the longest path problem on perfect graphs. In particular, motivated by the de nition of linear coloring on simplicial complexes, recently introduced in the context of algebraic topology, we introduce the colinear coloring on graphs, and propose a polynomial algorithm for colinearly coloring any graph G. Based on the colinear coloring, we de ne the
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Ιωαννίδου, Κυριακή
- Ioannidou, Kyriaki
Subjects
dc:subject × 19- Colinear και linear γραφήματα
- Colinear χρωματισμός
- Χρωματισμός, Πρόβλημα αρμονικού
- Πρόβλημα μέγιστων διαδρομών
- Πολυωνυμικός αλγόριθμος
- NP - πλήρη προβλήματα
- Γραφήματα, Τέλεια
- Colinear and linear graphs
- Colinear coloring
- Harmonious coloring problem
- Longest path problem
- Polynomial algorithm
- NP - completeness
- Perfect graphs
- Graph classes characterizations
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/18620