๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Computing biconnected components on a hypercube

โœ Scribed by Jinwoon Woo; Sartaj Sahni

Publisher
Springer US
Year
1991
Tongue
English
Weight
712 KB
Volume
5
Category
Article
ISSN
0920-8542

No coin nor oath required. For personal study only.

โœฆ Synopsis

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 were observed on dense graphs.

๐Ÿ“œ SIMILAR VOLUMES

A Stabilizing Algorithm for Finding Bico
A Stabilizing Algorithm for Finding Biconnected Components
โœ Mehmet Hakan Karaata ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 209 KB

In this paper, a self-stabilizing algorithm is presented for finding biconnected components of a connected undirected graph on a distributed or network model of computation. The algorithm is resilient to transient faults, therefore, it does not require initialization. The proposed algorithm is based

Distributed Computing on Anonymous Hyper
Distributed Computing on Anonymous Hypercube Networks
โœ Evangelos Kranakis; Danny Krizanc ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 245 KB

We consider the bit-complexity i.e.a, total number of bits transmitted of computing boolean functions on an anonymous canonically labeled n-dimensional hypercube network and give a characterization of the boolean functions computable on such a network as exactly those boolean functions which are inv

Computing Hough transforms on hypercube
Computing Hough transforms on hypercube multicomputers
โœ Sanjay Ranka; Sartaj Sahni ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Springer US ๐ŸŒ English โš– 843 KB

Efficient algorithms to compute the Hough transform on M1MD and SIMD hypercube multicomputers are developed. Our algorithms can compute p angles of the Hough transform of an N x N image, p < N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ~) processors. We also