# Parallel Algorithms for Zero-One Supply-Demand Problems

### Noam Nisan and Danny Soroker

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-87-368

August 1987

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-368.pdf

A technique which yields fast parallel algorithms for several zero-one supply-demand problems is presented. We give
*NC* algorithms for the following related problems:

(1) Given a sequence of supplies
*a*1, ...,
*a*n and demands
*b*1, ...,
*b*m, construct a zero-one flow pattern satisfying these constraints, where every supply vertex can send at most one unit of flow to each demand vertex.

(2) Given a sequence of positive and negative integers summing to zero, representing supplies and demands respectively, construct a zero-one flow pattern so that the net flow out of (into) each vertex is its supply (demand), where every vertex can send at most one unit of flow to every other vertex.

(3) Construct a digraph without self-loops with specified in- and out-degrees.

We extend our results to the case where the input represents upper bounds on supplies and lower bounds on demands.

BibTeX citation:

@techreport{Nisan:CSD-87-368, Author = {Nisan, Noam and Soroker, Danny}, Title = {Parallel Algorithms for Zero-One Supply-Demand Problems}, Institution = {EECS Department, University of California, Berkeley}, Year = {1987}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/6226.html}, Number = {UCB/CSD-87-368}, Abstract = {A technique which yields fast parallel algorithms for several zero-one supply-demand problems is presented. We give <i>NC</i> algorithms for the following related problems: <br />(1) Given a sequence of supplies <i>a</i>1, ..., <i>a</i>n and demands <i>b</i>1, ..., <i>b</i>m, construct a zero-one flow pattern satisfying these constraints, where every supply vertex can send at most one unit of flow to each demand vertex. <br />(2) Given a sequence of positive and negative integers summing to zero, representing supplies and demands respectively, construct a zero-one flow pattern so that the net flow out of (into) each vertex is its supply (demand), where every vertex can send at most one unit of flow to every other vertex. <br />(3) Construct a digraph without self-loops with specified in- and out-degrees. <p>We extend our results to the case where the input represents upper bounds on supplies and lower bounds on demands.} }

EndNote citation:

%0 Report %A Nisan, Noam %A Soroker, Danny %T Parallel Algorithms for Zero-One Supply-Demand Problems %I EECS Department, University of California, Berkeley %D 1987 %@ UCB/CSD-87-368 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/6226.html %F Nisan:CSD-87-368