go-v.orgdoi

Parallel Algorithms for Zero-One Supply-Demand Problems

Noam Nisan, Danny Soroker · SIAM Journal on Discrete Mathematics · 1989

  • DOI 10.1137/0402012
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1989

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 1989

Abstract

A technique that yields fast parallel algorithms for several zero-one supply-demand problems is presented. $NC$ algorithms are given for the following related problems: (1) Given a sequence of supplies $a_1 , \cdots ,a_n $ and demands $b_1 , \cdots ,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.

The results are extended to the case where the input represents upper bounds on supplies and lower bounds on demands.

Open the resolved locator · 10.1137/0402012

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 04:44 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0402012
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.