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

Περίληψη

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

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

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. […]
Διαβάστε τη διατριβή (Online)
Κατεβάστε τη διατριβή σε μορφή PDF (1.44 MB)  (Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)

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

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