Counting and selecting at random bipartite graphs with fixed degrees

Counting and selecting at random bipartite graphs with fixed degrees

0.00 Avg rating0 Votes
Article ID: iaor19921838
Country: France
Volume: 24
Start Page Number: 1
End Page Number: 14
Publication Date: May 1990
Journal: RAIRO Operations Research
Authors:
Abstract:

The paper first recalls the bijective mapping between bipartite simple graphs with specified degrees and 0/1 arrays with fixed sums of rows and columns, and these graphs are counted, using an enumerative procedure. Tables that contain the numbers of such graphs with at most 10 edges are given. Then a total order is put on this set, and an algorithm is provided to build the graph that has a given rank. If this rank is selected at random, uniformly or not, a random bipartite simple graph is obtained.

Reviews

Required fields are marked *. Your email address will not be published.