NC Coloring Algorithms for Permutation Graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S.
Andreou, M.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Nordic J. Computing
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We show that the problem of coloring a permutation graph of size n can be solved in O(logn logk) time using O(kn where 1 <k <n. We estimate the parameter k on random permutation graphs and show that the coloring problem can be solved in O(logn loglogn) time in the average-case on the CREW PRAM model of computation with O(n ) processors. Our computational strategy goes as follows: Given a permutation # or its corresponding permutation graph G[#], we first construct a directed acyclic graph G [#] using certain combinatorial properties of #, and then compute longest paths in the directed acyclic graph using divideand -conquer techniques. We show that the problem of coloring a permutation graph G[#] is equivalent to finding longest paths in its acyclic digraph G [#]. The best-known parallel algorithms for the same problem run in O(log n) time using O(n / logn) processors on the CREW PRAM model of computation.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής