Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών

Περίληψη σε άλλη γλώσσα

In 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

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/18620
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/18620
ND
18620
Εναλλακτικός τίτλος
New classes of perfect graphs and algorithms for coloring and longest path problems
Συγγραφέας
Ιωαννίδου, Κυριακή του Φραγκίσκος
Ημερομηνία
2009
Ίδρυμα
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Πληροφορικής
Εξεταστική επιτροπή
Νικολόπουλος Σταύρος
Κακλαμάνης Χρήστος
Παληός Λεωνίδας
Ζάχος Ευστάθιος
Ζησιμόπουλος Βασίλειος
Κοντογιάννης Σπυρίδων
Νομικός Χρήστος
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Λέξεις-κλειδιά
Colinear και linear γραφήματα; Colinear χρωματισμός; Χρωματισμός, Πρόβλημα αρμονικού; Πρόβλημα μέγιστων διαδρομών; Πολυωνυμικός αλγόριθμος; NP - πλήρη προβλήματα; Γραφήματα, Τέλεια
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
93 σ., εικ., ευρ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)