FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS
Φόρτωση...
Ημερομηνία
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Taylor & Francis
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Parallel Algorithms and Applications
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
ABSTRACT In this paper we present fast parallel algorithms for finding the cutpoints and bridges of an undirected graph G = (V,E) having n vertices. We start with the notion of partitioning a graph in a set of (mutually disjoint) adjacency-level sets, and we propose a parallel algorithm which computes these sets in time O(logL) using L · H · n2 processors on a CRCW-PRAM, where L < n and H < n. Based on the properties of the adjacency-level sets, we formulate parallel algorithms which locate all cutpoints and bridges of an undirected graph in constant time O(1) by using no more than L · H · n2 processors on a CRCW-PRAM computational model.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής