Professor Kazuo Iwama, Friday 15 September 1989: THEORY SEMINAR

Thread View: ut.theory

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by Marina Haloulos Tue, 12 Sep 1989 19:15

#20

Author: Marina Haloulos
Date: Tue, 12 Sep 1989 19:15

26 lines
1764 bytes

                            FLASH ANNOUNCEMENT
             (GB = Gailbraith Building, 35 St. George Street)

       -------------------------------------------------------------

                              THEORY SEMINAR
               GB119, at 3:00 p.m., Friday 15 September 1989

                           Professor Kazuo Iwama
                          Kyoto Sangyo University

     An 0(log n) Parallel Connectivity Algorithm on the Mesh of Buses

An 0(log n) parallel randomized algorithm for obtaining connected
components of an undirected graph is presented. The model is not the common
parallel random access machine (PRAM) but the mesh of buses (MB) which
consists of n sup 2 RAMs on the two dimensional mesh of communication
buses.  Unlike PRAMs, MBs are considered to be current realizable in a
similar degree as the mesh computer.  Their computation power, however,
appears to be much less than PRAMs; an obvious lower bound of sqrt N steps
exists to simulate PRAM's one step (`N` processors).  Nevertheless, our
achievement of the 0(log n) depth for this fundamental graph problem, which
is believed to be the best possible achieved only using PRAMs, demonstrates
that the unrealistically idealized communication scheme of PRAMs is
sometimes needlessly excessive for natural problems.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads