Parallel and Distributed Computation


A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby
Preliminary version in 17th STOC, 1985.
Final version in SIAM J. on Computing, November 1986, Vol. 15, No. 4, pp. 1036-1053.

Removing Randomness in Parallel Computation Without a Processor Penalty (412K)
Michael Luby
Preliminary version in 29th FOCS, 1988.
Final version in JCSS, Vol. 47, No. 2, 1993, pp. 250-286.

Efficient PRAM Simulation on a Distributed Memory Machine (315K)
Richard Karp, Michael Luby, Friedhelm Meyer auf de Heide
Preliminary version in 24th STOC, 1992.
Final version in Algorithmica, Vol. 16, No. 4/5, Oct/Nov 1996, pp. 517-542.

A Parallel Approximation Algorithm for Positive Linear Programming (158K)
Michael Luby, Noam Nisan
25th STOC, 1993.

A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula
Stephen Cook, Michael Luby
Information Processing Letters, Vol. 27, March 1988, pp. 141-145.

Network Decomposition and Locality in Distributed Computation (227K)
Baruch Awerbuch, Andrew Goldberg, Michael Luby, Serge Plotkin
30th FOCS, 1989.