Abstract | ||
---|---|---|
We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ParityL subset of NC^2. This extends the techniques of [Valiant], [Braverman, Kulkarni, Roy] and [Bj\"orklund, Husfeldt], and yields a (randomized) parallel algorithm for shortest 2-disjoint paths improving upon the recent result from (randomized) polynomial time. We also recognize the disjoint paths problem as a special case of finding disjoint cycles, and present (randomized) parallel algorithms for finding a shortest cycle and shortest 2-disjoint cycles passing through any given fixed number of vertices or edges. |
Year | DOI | Venue |
---|---|---|
2021 | 10.4230/LIPIcs.MFCS.2021.36 | MFCS |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Samir Datta | 1 | 0 | 1.69 |
Kishlaya Jaiswal | 2 | 0 | 0.34 |