Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12488Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Asdre, K. | en |
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.contributor.author | Papadopoulos, C. | en |
| dc.date.accessioned | 2015-11-24T17:21:37Z | - |
| dc.date.available | 2015-11-24T17:21:37Z | - |
| dc.identifier.issn | 0743-7315 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/12488 | - |
| dc.rights | Default Licence | - |
| dc.subject | p-4-sparse graphs | en |
| dc.subject | cographs | en |
| dc.subject | modular decomposition | en |
| dc.subject | parallel algorithms | en |
| dc.subject | path cover | en |
| dc.subject | modular decomposition | en |
| dc.subject | algorithm | en |
| dc.subject | efficient | en |
| dc.subject | cographs | en |
| dc.title | An optimal parallel solution for the path cover problem on P-4-sparse graphs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | DOI 10.1016/j.jpdc.2006.08.011 | - |
| heal.identifier.secondary | <Go to ISI>://000243614700005 | - |
| heal.identifier.secondary | http://ac.els-cdn.com/S0743731506001778/1-s2.0-S0743731506001778-main.pdf?_tid=2df661ff80562dcb3c6b05fafcfb64d8&acdnat=1339399732_3d485c9bb5062e2cfd0001a15276189b | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2007 | - |
| heal.abstract | Nakano et al. [A time-optimal solution for the path cover problem on cographs, Theoret. Comput. Science 290 (2003) 1541-1556] presented a time- and work-optimal algorithm for finding the smallest number of vertex-disjoint paths that cover the vertices of a cograph and left open the problem of applying their technique into other classes of graphs. Motivated by this issue we generalize their technique and apply it to the class of P-4-sparse graphs, which forms a proper superclass of cographs. We show that the path cover problem on P-4-sparse graphs can also be optimally solved. More precisely, given a P-4-sparse graph G on n vertices and its modular decomposition tree, we describe an optimal parallel algorithm which returns a minimum path cover of G in O (log n) time using O (n /log n) processors on the EREW PRAM model. Our results generalize previous results and extend the family of perfect graphs admitting optimal solutions for the path cover problem. (C) 2006 Elsevier Inc. All rights reserved. | en |
| heal.publisher | Elsevier | en |
| heal.journalName | Journal of Parallel and Distributed Computing | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Asdre-2007-An optimal parallel.pdf | 478.75 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
