Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Reif, John H. |
| Abstract | This paper gives output sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient than previous algorithms for problems with sufficiently small output size. Inputs are n n matrices over a fixed ground feld. Let P (n) and M(n) bethe PRAM processor bounds for O(log n) time multiplication of two degree n polynomials, and n n matrices, respectively. Let T (n) be the time bounds, using M(n) processors, for testing if an n n matrix is nonsingular, and if so, computing its inverse. We compute the rank R of a matrix in randomized parallel time O(log n + T (R) log R) using nP (n) +M(R) processors (P (n)+RP (R) processors for constant displacement rank matrices, e.g. Toeplitz matrices). We find a maximum linearly independent subset (MLIS) of an n-set of n-dimensional vectors in time O(T (n) log n) using M(n) randomized processors and we also give output sensitive algorithms for this problem. Applications include output sensitive algorithms for finding: (i) a size R maximum matching in an n-vertex graph using time O(T (R) log n) and nP (n)=T (R)+RM(R) processors, and (ii) a maximum matching in an n-vertex bipartite graph, with vertex subsets of sizes n1 sors. n2; using time O(T (n1) log n) and nP (n)=T (n1)+n1M(n1) proces- |
| File Format | |
| Journal | Proceedings of Spatial Cognition |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | N-vertex Bipartite Graph Toeplitz Matrix Size N1 Sors Degree Polynomial Output Sensitive Parallel Algorithm Linear Algebra Problem Size Maximum Matching Randomized Parallel Time Output Sensitive Algorithm Parallel Output Sensitive Algorithm Vertex Subset Bethe Pram Processor Bound Time Multiplication N-dimensional Vector Constant Displacement Rank Matrix Previous Algorithm Small Output Size N-vertex Graph Ground Feld Maximum Matching Maximum Linearly Independent Subset Output Size |
| Content Type | Text |
| Resource Type | Article |
