A Fast Parallel Algorithm for MinimumCost Small Integral Flows
(2015) In Algorithmica 72(2). p.607619 Abstract
 We present a new approach to the minimumcost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for nonidentity with zero. In effect, we show that a minimumcost 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(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimumcost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC... (More)
 We present a new approach to the minimumcost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for nonidentity with zero. In effect, we show that a minimumcost 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(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimumcost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/7424973
 author
 Lingas, Andrzej ^{LU} and Persson, Mia
 organization
 publishing date
 2015
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Maximum integral flow, Minimumcost flow, Polynomial verification, Parallel algorithms, Randomized algorithms, Time complexity, Processor, complexity
 in
 Algorithmica
 volume
 72
 issue
 2
 pages
 607  619
 publisher
 Springer
 external identifiers

 wos:000354066300011
 scopus:84929061709
 ISSN
 01784617
 DOI
 10.1007/s0045301398651
 language
 English
 LU publication?
 yes
 id
 6e9dc9d2b7b04af7b3da74273babb135 (old id 7424973)
 date added to LUP
 20150626 07:16:37
 date last changed
 20170924 03:10:53
@article{6e9dc9d2b7b04af7b3da74273babb135, abstract = {We present a new approach to the minimumcost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for nonidentity with zero. In effect, we show that a minimumcost 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(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimumcost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.}, author = {Lingas, Andrzej and Persson, Mia}, issn = {01784617}, keyword = {Maximum integral flow,Minimumcost flow,Polynomial verification,Parallel algorithms,Randomized algorithms,Time complexity,Processor,complexity}, language = {eng}, number = {2}, pages = {607619}, publisher = {Springer}, series = {Algorithmica}, title = {A Fast Parallel Algorithm for MinimumCost Small Integral Flows}, url = {http://dx.doi.org/10.1007/s0045301398651}, volume = {72}, year = {2015}, }