On the performance of the first-fit coloring algorithm on permutation graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Elsevier
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Information Processing Letters
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper we study the performance of a particular on-line coloring algorithm, the First-Fit or Greedy algorithm, on a class of perfect graphs namely the permutation graphs. We prove that the largest number of colors chi (FF)(G) that the First-Fit coloring algorithm (FF) needs on permutation graphs of chromatic number chi>(*) over bar * (G) = chi when taken over all possible vertex orderings is not linearly bounded in terms of the off-line optimum, if X is a fixed positive integer. Specifically, we prove that for any integers chi > 0 and k greater than or equal to 0, there exists a permutation graph G on n vertices such that chi>(*) over bar * (G) = chi and chi (FF)(G) greater than or equal to 1/2 ((chi (2) + chi) + k(chi (2) - chi)), for sufficiently large n. Our result shows that the class of permutation graphs P is not First-Fit X-bounded; that is, there exists no function f such that for all graphs G epsilon P, chi (FF)(G) less than or equal to f(omega>(*) over bar * (G)). Recall that for perfect graphs omega>(*) over bar * (G) = chi>(*) over bar * (G), where omega>(*) over bar * (G) denotes the clique number of G. (C) 2000 Elsevier Science B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
on-line coloring, first-fit algorithm, algorithms, permutation graphs, perfect graphs, combinatorial problems, online
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000165067500006
http://ac.els-cdn.com/S0020019000001095/1-s2.0-S0020019000001095-main.pdf?_tid=a9dac96db8369f393e4bb6da6aac4516&acdnat=1339410025_4bf2e8c2168b8a47e38f9368d587d6a5
http://ac.els-cdn.com/S0020019000001095/1-s2.0-S0020019000001095-main.pdf?_tid=a9dac96db8369f393e4bb6da6aac4516&acdnat=1339410025_4bf2e8c2168b8a47e38f9368d587d6a5
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών