🚀 go-pugleaf

                            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.