A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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 multivariate 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(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
  • Beräkningsmatematik

Nyckelord

Originalspråkengelska
Sidor (från-till)607-619
TidskriftAlgorithmica
Volym72
Utgivningsnummer2
StatusPublished - 2015
PublikationskategoriForskning
Peer review utfördJa