On the parallel computation of the biconnected and strongly connected co-components of graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Applied Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n + in) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search. Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in O(log(2) n) time using O((n + m)/log(2)- n) processors. The strong co-connectivity algorithm can also be parallelized to yield an O(log(2) n)-time and O(m(1.188)/ log n)-processor solution. As a byproduct, we obtain a simple optimal O(log n)-time parallel co-connectivity algorithm. Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself. (c) 2007 Elsevier B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
biconnected and co-biconnected components, strongly connected and co-connected components, co-biconnectivity algorithms, strong co-connectivity algorithms, parallel algorithms, algorithms, efficient, search
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής