Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10740Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.date.accessioned | 2015-11-24T17:00:17Z | - |
| dc.date.available | 2015-11-24T17:00:17Z | - |
| dc.identifier.issn | 0166-218X | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10740 | - |
| dc.rights | Default Licence | - |
| dc.subject | permutation graphs | en |
| dc.subject | perfect graphs | en |
| dc.subject | coloring problem | en |
| dc.subject | parallel algorithms | en |
| dc.subject | trees | en |
| dc.subject | complexity | en |
| dc.subject | pram models | en |
| dc.subject | maximal independent sets | en |
| dc.subject | fast algorithms | en |
| dc.title | Coloring permutation graphs in parallel | 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 | 2002 | - |
| heal.abstract | A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log(2) n) time using O(n(2)/log n) processors on the CREW PRAM model. Specifically, given a permutation pi we construct a tree T-*[pi], which we call coloring-permutation tree, using certain combinatorial properties of pi. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree. (C) 2002 Elsevier Science B.V. All rights reserved. | en |
| heal.journalName | Discrete Applied Mathematics | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-2002-Coloring permutation graphs in parallel.pdf | 346.1 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
