✦ LIBER ✦

Parallel strong orientation on a mesh connected computer

✍ Scribed by Manfred Schimmler

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 411 KB
Volume: 17
Category: Article
ISSN: 0167-8191
DOI: 10.1016/s0167-8191(05)80055-9

No coin nor oath required. For personal study only.

✦ Synopsis

Schimmler, M., Parallel strong orientation on a mesh connected computer, Parallel Computing 17 (1991) 657-664.

We present a solution for the following problem: given an undirected bridgeless connected graph G = (V, E), find an orientation of each edge such that the resulting directed graph is strongly connected. We assume the input graph to be given as an adjacency matrix stored in the processors of a mesh connected processor array such that each processor contains one entry. Our algorithm is a modification of Tarjan and Vishkin's strong orientation method [13] for a CREW PRAM. It takes time O(n) for an n-vertex graph which is asymptotically optimal for the considered computer model.

📜 SIMILAR VOLUMES

Parallel processing of linear quadtrees

Parallel processing of linear quadtrees on a mesh-connected computer

✍ Yubin Hung; Azriel Rosenfeld 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 423 KB

Mesh-connected parallel computer PAX for

Mesh-connected parallel computer PAX for scientific applications

✍ Tsutomu Hoshino; Tomonori Shirakawa; Keiichi Tsuboi 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 909 KB

Parallel B-Spline Surface Fitting on Mes

Parallel B-Spline Surface Fitting on Mesh-Connected Computers

✍ Kuo-Liang Chung; Wen-Ming Yan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 257 KB

Parallel voronoi diagram in L1 (L∞) metr

Parallel voronoi diagram in L1 (L∞) metric on a mesh-connected computer

✍ Chang-Sung Jeong 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 672 KB

Jeong, C.S., Parallel Voronoi diagram in L 1 (L~) metric on a mesh-connected computer, Parallel Computing 17 (1991) 241-252 In this paper, we consider the problem of constructing a Voronoi diagram in L~(L.o ) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An o(vrn)

An improved parallel algorithm for const

An improved parallel algorithm for constructing voronoi diagram on a mesh-connected computer

✍ Chang-Sung Jeong 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 455 KB

Fault-Tolerant Recursive Least-Squares C

Fault-Tolerant Recursive Least-Squares Computations on a Mesh-Connected Parallel Processor

✍ Albert Y. Zomaya; Adrian Yates; Stephan Olariu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 316 KB

Recursive least squares (RLS) is a popular iterative method used for the modeling of systems while in operation. RLS provides an estimate for unknown parameters of a system based on some known parameters and inputs and outputs of that system. This technique is used frequently in digital signal proce