NC Coloring Algorithms for Permutation Graphs
| dc.contributor.author | Nikolopoulos, S. | en |
| dc.contributor.author | Andreou, M. | en |
| dc.date.accessioned | 2015-11-24T17:03:09Z | |
| dc.date.available | 2015-11-24T17:03:09Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11136 | |
| dc.rights | Default Licence | - |
| dc.title | NC Coloring Algorithms for Permutation Graphs | en |
| heal.abstract | 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 |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.journalName | Nordic J. Computing | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 1999 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: