On the Strongly Connected and Biconnected Components of the Complement of Graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, Stavros D.
Palios, Leonidas
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Electronic Notes in Discrete Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we consider the problems of computing the strongly connected components and the biconnected components of the complement of a given graph. In particular, for a directed graph G on n vertices and m edges, we present a simple algorithm for computing the strongly connected components of G ? which runs in optimal O ( n + m ) time. The algorithm can 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 very simple optimal parallel co-connectivity algorithm. Additionally, we establish properties which, for an undirected graph on n vertices and m edges, enable us to describe an O ( n + m ) -time algorithm for computing the biconnected components of G ? , which can be parallelized resulting in an algorithm that runs in O ( log n ) time using O ( ( n + m ) / log n ) processors.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής