NDLI: A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

Content Provider	Springer Nature Link
Author	Lingas, Andrzej Persson, Mia
Copyright Year	2014
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)+log2(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.
Starting Page	607
Ending Page	619
Page Count	13
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	72
Issue Number	2
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Maximum integral flow Minimum-cost flow Polynomial verification Parallel algorithms Randomized algorithms Time complexity Processor complexity Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A fast parallel algorithm for minimum-cost small integral flows

A simpler minimum spanning tree verification algorithm

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

Optimal parallel verification of minimum spanning trees in logarithmic time

Communication Complexity of Quasirandom Rumor Spreading

Maximum Series-Parallel Subgraph

Computing Minimum Cuts by Randomized Search Heuristics

Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

Similar Documents

A fast parallel algorithm for minimum-cost small integral flows

A simpler minimum spanning tree verification algorithm

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

Optimal parallel verification of minimum spanning trees in logarithmic time

Communication Complexity of Quasirandom Rumor Spreading

Maximum Series-Parallel Subgraph

Computing Minimum Cuts by Randomized Search Heuristics

Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows