Loading...
Please wait, while we are loading the content...
Similar Documents
A fast parallel algorithm for minimum-cost small integral flows
| Content Provider | arXiv |
|---|---|
| Author | Lingas, Andrzej Persson, Mia |
| Date of Submission | 2012-10-01 |
| Abstract | We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(k\log (kn)+\log^2 (kn)) time and using 2^{k}(kn)^{O(1)} processors. Thus, in particular, for the minimum-cost flow of value O(\log n), we obtain an RNC^2 algorithm. |
| Related Links | https://arxiv.org/pdf/1210.0340.pdf |
| arXiv | 1210.0340 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Distributed, Parallel, and Cluster Computing Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
