************ Minimum spanning tree ************

Boruvka's algorithm constructs the minimum spanning tree in a way that
is well suited for parallel computation.  The algorithm starts with a
forest of n trees each has one vertex.  Each tree in the forest finds
the minimum cost edge adjacent to it.  Two trees are combined if an
edge connecting them is selected.  Finally the forest is combined into
the minimum spanning tree.

@article{,
author = "B. Boruvka",
title =  "O jistem problemu minimalnim",
journal   = "Praca Moravske Prirodovedecke Spolecnosti",
volume = "3", 
year =  "1926 (in Czech)"}

Kruskal's algorithm finds the minimum spanning tree by sorting the
edge according to their costs, then repeatedly selecting the minimum
cost edge that will not form a cycle among those edges that have been
selected.

@article{,
author = "J. B. Kruskal",
title =  "On the shortest spanning subtree of a graph and the
traveling salesman problem",
journal   = "Proc. Amer. Math. Soc.",
volume = "7", 
year =  "1956"}

Prim's algorithm constructs the minimum spanning tree by adding one
vertex at a time into the spanning tree.  The initial tree T consists
of one arbitrary vertex.  In the next n-1 phases the vertex adjacent to
the minimum cost edge incident to T is included into T.  Finally the
set T contains the minimum spanning tree.

@article{,
author = "E. W. Dijkatra",
title =  "A note on two problems in connextion with graphs",
journal   = "Numer. Math.",
volume = "1", 
year =  "1959"}

@article{,
author = "R. C. Prim",
title = "Shortest connection networks and some generalizations",
journal = "Bell System Tech. J.",
volume = "36", 
year =  "1957"}


Cheriton-Tarjan's algorithm finds the minimum spanning tree by
implementing Boruvka's edge selection process in a round-robin
fashion.  The forest in Boruvka's algorithm is stored in a queue and
one tree is selected at a time to find the minimum cost edge adjacent
to it.  The running time is O(m log log n) by a careful data structure
design.

@article{,
author = "D. Cheriton and R. E. Tarjan",
title = "Finding minimum spanning trees",
journal = "SIAM J. Comput.",
volume = "5", 
year =  "1976"}

Given a minimum spanning tree, this algorithm finds for each tree edge
e a minimum-cost substitute edge e' such that if e is deleted from the
original graph, replacing it by e' produces a minimum spanning tree in
the new graph.

@article{,
author = "R. E. Tarjan",
title = "Application of path compression on balanced trees",
journal = "J. Assoc. COmput. Mach.",
volume = "26", 
year =  "1979"}

Magga-Plotkin's algorithm converts the minimum spanning tree problem
into a problem similar to finding the shortest path.  The algorithm is
based on the observation that an edge (i,j) is in the minimum spanning
tree if and only if every path of two or more linking i and j has an
edge with higher cost than the cost of (i,j).  Therefore by computing
the shortest path for every pair of vertices (where the cost of a path
is the cost of the heaviest edge on this path), we can decide if an
edge is in the minimum spanning tree.

@article{,
author = "B. Magga and S. Plotkin",
title =  "Minimum cost spanning tree as a path-finding problem",
journal = "Information processing Letters",
volume = "26(6)", 
year =  "1988"}


************ Connect components ************

An efficient parallel algorithm for connected components problem.
The algorithm takes O(log N) phases to combine a forest of graph
vertices into connected components.  An CREW PRAM implementation is
also presented.

@article{,
author = "D.S. Hirschberg and A.K. Chandra and D.V. Sarwate",
title =  "Computing connected components on parallel computers",
journal = "Comm. of ACM",
volume = "22", 
year =  "1979"}


An EREW implementation of Hischberg-Chandra-Sarwate connected
component algorithm.  

@article{,
author = "D. Nath and S.N. Maheshwari",
title =  "Parallel algorithms for the connected components and minimum
spanning tree problems",
journal = "Inf. Proc. Letters",
volume = "14", 
year =  "1982"}


An CRCW PRAM implementation of Hischberg-Chandra-Sarwate connected
component algorithm.  The time bound is O(log n) using O(m + n)
processors. 

@article{,
author = "B. Awerbuch and Y. Shiloach",
title =  "New connectivity and MSF algorithms for shuffle-exchange
network and PRAM",
journal = "IEEE Trans. Comput.",
volume = "36", 
year =  "1987"}

@article{,
author = "Y. Shiloach and U. Vishkin",
title =  "An O(log n) parallel connectivity algorithm",
journal = "J. Algorithms",
volume = "2", 
year =  "1982"}


An parallel algorithm based on Hischberg-Chandra-Sarwate connected
component algorithm.  It uses more elaborate techniques based on
optimal list ranking.  The running time on an ARBITRARY CRCW PRAM is
O(log n) with O((m + n) \alpha(m, n) / log n) processors.  \alpha(m,
n) is the inverse Ackerman function.

@inproceedings{,
author = "R. Cole and U. Vishkin",
title =  "Approximate and exact parallel scheduling with applications
to list, tree and graph problems",
booktitle  = "Proceeding of the 27th Ann. IEEE Symp. on Foundations of
Computer Science",
year = "1986"}

An randomized optimal O(log n) algorithm for finding connected
components on an ARBITRARY CRCW PRAM.

@inproceedings{,
author = "H. Gazit",
title =  "An optimal randomized parallel algorithm for finding
connected components in a graph",
booktitle  = "Proceeding of the 27th Ann. IEEE Symp. on Foundations of
Computer Science",
year = "1986"}


[Need to put some explanation here]

@techreport{,
author = "T. Christopher", 
title = "An implementation of Warshall's algorithm for transitive
closure on a cellular computer",
institution =  "Institute for Computer Research, University of Chicago",
number =  "36", 
year = "1973"}

@inproceedings{,
title = "Direct VLSI implementation of combinatorial algorithms",
author =  "L. Guibas and H. Kung and C. Thompson",
booktitle  = "Proceeding of the Caltech Conference on Very Large Scale
Integration", 
year = "Jan 1979"}

@article{,
author = "M. Atllah and S. Hambrusch",
title =  "Solving tree problems on a mesh-connected processor array",
journal = "Information and Computation",
volume = "69(1-3)", 
year =  "1986"}