Αλγόριθμοι και περιπλοκότητα: χρωματισμοί γράφων και υπεργράφων

Περίληψη

Μελετάμε διάφορους χρωματισμούς κορυφών για γράφους και υπεργράφους. Επικεντρωνόμαστε στους χρωματισμούς χωρίς συγκρούσεις. Οι χρωματισμοί χωρίς συγκρούσεις έχουν εφαρμογές στην αποδοτική ανάθεση συχνοτήτων σε κυψελωτά δίκτυα. Δείχνουμε πώς σχετίζονται οι χρωματισμοί χωρίς συγκρούσεις ως προς μονοπάτια γράφων με άλλα προβλήματα χρωματισμού γράφων, όπως: διατεταγμένοι χρωματισμοί (ή αλλιώς κατάταξη κορυφών), χρωματισμοί χωρίς τετράγωνα (συμβολοσειρές), και κλασικοί χρωματισμοί γράφων. Αποδεικνύουμε ιδιότητες των παραπάνω χρωματισμών καθώς και άνω και κάτω φράγματα για τα χρώματα που απαιτούνται για διάφορες κλάσεις γράφων (αλυσίδες, δακτύλιοι, δένδρα, πλέγματα). Αναλύουμε διάφορες εκδοχές του χρωματισμού χωρίς συγκρούσεις για γράφους αλυσίδες και γράφους δακτυλίους ως προς μονοπάτια. Στην περίπτωση των αλυσίδων το πρόβλημα είναι επίσης γνωστό ως χρωματισμός χωρίς συγκρούσεις ως προς διαστήματα. Για μία άμεση (online) εκδοχή του προβλήματος όπου οι κορυφές του γράφου εμφανίζονται μία μία ...
περισσότερα

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

We study several vertex coloring problems for graphs and hypergraphs. We concentrate on conflict-free coloring. The conflict-free coloring problem has applications in efficient frequency assignment in cellular networks. We show the relation of conflict-free coloring paths of graphs with other graph coloring problems, like ordered coloring (also known as vertex ranking), square free coloring, and traditional graph coloring. We prove properties of the above colorings and upper and lower bounds for the colors needed for several graph classes (chains, rings, trees, grids). We analyze several versions of conflict-free coloring chain and ring graphs with respect to paths. For chain graphs, the problem is also known as conflict- free coloring with respect to intervals. For an online version of the problem where vertices of the graph appear one by one, and an algorithm has to commit on the color of a vertex before seeing the positions of the future vertices, we analyze the first-fit greedy and ...
περισσότερα

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

DOI
10.12681/eadd/16645
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/16645
ND
16645
Εναλλακτικός τίτλος
Algorithms and complexity: graph and hypgraph colorings
Συγγραφέας
Χείλαρης, Παγαγιώτης
Ημερομηνία
2007
Ίδρυμα
Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών
Εξεταστική επιτροπή
Ζάχος Ευστάθιος
Σελλής Τίμος
Κολέτσος Γιώργος
Αφράτη Φώτω
Δελής Αλέξης
Παπασπύρου Νίκος
Παγουρτζής Άρης
Επιστημονικό πεδίο
Επιστήμες Μηχανικού και Τεχνολογία
Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
Λέξεις-κλειδιά
Χρωματισμός; Γράφοι; Υπεργράφος; Αλγόριθμοι
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
111 σ., εικ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.