文章基本信息

标题：Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles
本地全文：下载
作者：Datta, Samir ; Jaiswal, Kishlaya
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：202
DOI：10.4230/LIPIcs.MFCS.2021.36
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ⨁L ⊆ NC². This extends the techniques of Valiant [Leslie G. Valiant, 1979], Braverman, Kulkarni and Roy [Mark Braverman et al., 2009] and Björklund and Husfeldt [Andreas Björklund and Thore Husfeldt, 2019] and yields a (randomized) parallel algorithm for shortest two disjoint paths improving upon the recent (randomized) polynomial time algorithm [Andreas Björklund and Thore Husfeldt, 2019].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 two disjoint cycles passing through any given fixed number of vertices or edges.
关键词：permanent mod powers of 2;parallel computation;graphs;shortest disjoint paths;shortest disjoint cycles