An optimal parallel solution for the path cover problem on P-4-sparse graphs
| 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.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.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| 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.journalName | Journal of Parallel and Distributed Computing | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2007 | - |
| heal.publisher | Elsevier | en |
| 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
- Περιγραφή: