Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles
From MaRDI portal
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.
This page was built for publication: Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168451)
