The algorithm we implemented here generates random simple connected graphs with prescribed degree sequence.
This algorithm is described in the article: 'Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence', in proc. of the 11th Conference of Computing & Combinatoric (COCOON 2005), LNCS 3595, pp 440-449. You may download a preprint here:
Efficient and simple generation of random simple connected graphs with prescribed degree sequence
Note that a full version, containing approximately twice as much material,
is currently submitted to an international journal.
The software provided here is for demonstration purposes. Use it at your own risk.
However, we did not encounter any trouble on Linux (32-bit and 64-bit configurations), Cygwin, Windows 98 SE or Windows XP, so it should work fine for most configurations.
Sources (compilables with g++):
Windows executables (in command prompt environment): .zip(140Kb), .rar(80Kb).
Documentation and Bibliography
For a brief desciption of the software, see the README file.
For more information about the uniform random generation of graphs with prescribed degree sequence, see the following papers:
This software is published under the GNU General Public License .
Back to home page