  We consider the problem of constructing a bipartite graph whose degrees lie
in prescribed intervals. Necessary and sufficient conditions for the existence
of such graphs are well-known. However, existing realization algorithms suffer
from large running times. In this paper, we present a realization algorithm
that constructs an appropriate bipartite graph G=(U,V,E) in O(|U| + |V| + |E|)
time, which is asymptotically optimal. In addition, we show that our algorithm
produces edge-minimal bipartite graphs and that it can easily be modified to
construct edge-maximal graphs.

Data Structures and Algorithms;Discrete Mathematics