Efficient parallel recognition of cographs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Applied Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P-4. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in O(log(2) n) time and require O((n + m)l log n) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29-44) and take advantage of the optimal O(log n)-time computation of the coconnected components of a general graph (Theory Comput. Systems 37 (2004) 527-546) and of an optimal O(log n)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29-44; J. Algorithms 15 (1993) 284-313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P-4 whenever our algorithms decide that the input graphs are not cographs. (c) 2005 Elsevier B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
perfect graphs, cographs, cotree, connected and co-connected components, parallel algorithms, parallel recognition, certifying algorithms, complement reducible graphs, p4-sparse graphs, linear-time, algorithm
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής