An optimal parallel solution for the path cover problem on P-4-sparse graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Asdre, K.
Nikolopoulos, S. D.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Elsevier
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Journal of Parallel and Distributed Computing
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
p-4-sparse graphs, cographs, modular decomposition, parallel algorithms, path cover, modular decomposition, algorithm, efficient, cographs
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000243614700005
http://ac.els-cdn.com/S0743731506001778/1-s2.0-S0743731506001778-main.pdf?_tid=2df661ff80562dcb3c6b05fafcfb64d8&acdnat=1339399732_3d485c9bb5062e2cfd0001a15276189b
http://ac.els-cdn.com/S0743731506001778/1-s2.0-S0743731506001778-main.pdf?_tid=2df661ff80562dcb3c6b05fafcfb64d8&acdnat=1339399732_3d485c9bb5062e2cfd0001a15276189b
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών