Raphael A. Finkel, Marvin Solomon, Michael L. Horowitz

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations


In order to fully utilize the speed and power inherent in a computer network, emphasis must be placed on the development of parallel (as opposed to sequential) algorithms. This paper investigates concurrent algorithms designed to impose a logical structure on top of the physical computer network, such as a pairing of the processors along communication lines. These algorithms are interesting not only for their relationship to parallel algorithms in general, but also because the resulting structure may be used as a basis for writing other parallel algorithms. The algorithms discussed form three types of structures on the network. These three problems have been chosen because their results are dependent upon the physical network configuration and because they apply to the solution of other network problems. Pairing algorithms match each node of the network with a direct neighbor. Spanning tree algorithms impose a tree on the network so that a unique path exists between any two processors in the network. The last problem considered is that of forming hierarchies of processors. One step in developing a hierarchy is the formation of processor cliques. Each clique should be of a certain size and one processor in each clique is designated as the ″leader.″ A good solution should try to minimize the average radius of each clique.

Original languageEnglish
Number of pages6
StatePublished - 1979
EventUnknown conference - New York City, NY, USA
Duration: Jun 4 1979Jun 7 1979


ConferenceUnknown conference
CityNew York City, NY, USA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'DISTRIBUTED ALGORITHMS FOR GLOBAL STRUCTURING.'. Together they form a unique fingerprint.

Cite this