Publications [#332093] of John H. Reif

Conference articles PUBLISHED

1. Cheriyan, J; Reif, JH, Parallel and output sensitive algorithms for combinatorial and linear algebra problems, Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures Spaa 1993 (August, 1993), pp. 50-56, ACM Press, ISBN 9780897915991 [doi]
   (last updated on 2026/01/15)

   Abstract:
   The notion of output sensitive parallel algorithms for linear algebra problems is formalized in this paper, and such algorithms are presented for finding the rank of an n x n matrix in randomized parallel time 0(log n + logR) using 0(n2 + M(R)) processors, and for finding a maximum linearly independent subset of an n-set of n-dimensional vectors in randomized parallel time 0((log n) log3 R) using (n2 + RM(R)) processors (R is the size of the subset). Also, output sensitive TLSfC algorithms for some combinatorial problems are developed. The best TLSfC algorithm known for finding a maximum linearly independent subset of an n-set of n-dimensional vectors is given; the randomized parallel time is 0(logn) using 0(M(n)) processors. Note that this problem is likely harder than the problem of rinding a basis for the space spanned by the input vectors. An output sensitive TUfC algorithm for computing greatest common divisors of polynomials is developed. This result is due to the second author. A minimum vertex cover in a bipartite graph and a minimum X-Y vertex separator in a digraph can be found in randomized parallel time 0(log3 n) using 0(M(n)) processors (n is the number of vertices). This result is due to the first author. Note that this is the best complexity bound known for TLhfC algorithms, and matches the best TLSfC complexity bounds for the associated decision problems.