PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, Stavros D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Taylor & Francis
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Parallel Algorithms and Applications
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We present a fast parallel algorithm for finding the blocks or biconnected components of an undirected graph G = (V,E ) having n vertices and m edges. Our techniques arc based on partitioning the vertex set V into adjacency-level sets using information contained in the distance matrix D of the graph. Let t D and p D be the time and number of processors, respectively, for the computation of the distance matrix of a graph G on a CRCW-PRAM computational model. We show that the location of all cut vertices and bridges of a graph can be done in time O(logδ + t D) by using O(n m/t d) processors, where δ is the maximum degree of a vertex in G. Based on these results, we define a digraph G d and we prove certain properties on its distance matrix leading to a parallel block-finding algorithm running in time O(logδ + t D) with O(n m/t D) processors on the same computational model. We also show that other connectivity-related problems can be efficiently solved using distance matrices.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής