Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11136Full metadata record
| DC Field | Value | Language |
|---|---|---|
| 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.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 1999 | - |
| 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.journalName | Nordic J. Computing | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-1999-NC Coloring Algorithms for Permutation Graphs.pdf | 212.19 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
