Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10816Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.contributor.author | Palios, L. | en |
| dc.date.accessioned | 2015-11-24T17:00:48Z | - |
| dc.date.available | 2015-11-24T17:00:48Z | - |
| dc.identifier.issn | 0196-6774 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10816 | - |
| dc.rights | Default Licence | - |
| dc.subject | parallel algorithms | en |
| dc.subject | perfectly orderable graphs | en |
| dc.subject | p-4-comparability graphs | en |
| dc.subject | p-4-components | en |
| dc.subject | recognition | en |
| dc.subject | acyclic p-4-transitive orientation | en |
| dc.subject | pram computation | en |
| dc.subject | perfectly orderable graphs | en |
| dc.subject | recognition algorithm | en |
| dc.subject | permutation graphs | en |
| dc.subject | comparability | en |
| dc.subject | cographs | en |
| dc.subject | complexity | en |
| dc.title | Parallel algorithms for P-4-comparability graphs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1016/j.jalgor.2003.11.005 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2004 | - |
| heal.abstract | We consider two problems pertaining to P-4-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P-4-comparability graph and the problem of producing an acyclic P-4-transitive orientation of such a graph. Sequential algorithms for these problems have been presented by Hoang and Reed and very recently by Raschle and Simon, and by Nikolopoulos and Palios. In this paper, we establish properties of P-4-comparability graphs which allow us to describe parallel algorithms for the recognition and orientation problems on this class of graphs; for a graph on n vertices and in edges, our algorithms run in O(nm) time and require O(nm/log n) processors on the CREW PRAM model. Since the currently fastest sequential algorithms for these problems run in O(nm) time, our algorithms are cost-efficient; moreover, to the best of our knowledge, this is the first attempt to introduce parallelization in problems involving P-4-comparability graphs. Our approach relies on the parallel computation and proper orientation of the P-4-components of the input graph. (C) 2003 Elsevier Inc. All rights reserved. | en |
| heal.journalName | Journal of Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Nikolopoulos-2004-Parallel algorithms.pdf | 355.35 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
