On the parallel computation of the biconnected and strongly connected co-components of graphs
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.contributor.author | Palios, L. | en |
| dc.date.accessioned | 2015-11-24T17:01:33Z | |
| dc.date.available | 2015-11-24T17:01:33Z | |
| dc.identifier.issn | 0166-218X | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10943 | |
| dc.rights | Default Licence | - |
| dc.subject | biconnected and co-biconnected components | en |
| dc.subject | strongly connected and co-connected components | en |
| dc.subject | co-biconnectivity algorithms | en |
| dc.subject | strong co-connectivity algorithms | en |
| dc.subject | parallel algorithms | en |
| dc.subject | algorithms | en |
| dc.subject | efficient | en |
| dc.subject | search | en |
| dc.title | On the parallel computation of the biconnected and strongly connected co-components of graphs | en |
| heal.abstract | 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. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | DOI 10.1016/j.dam.2007.03.016 | - |
| heal.journalName | Discrete Applied Mathematics | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2007 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: