Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence
We address here the problem of generating randoM graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm designed for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity). We focus on a family of heuristics for which we prove optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for typical real-world degree distributions, which outperforms the first one. Assuming a conjecture, we finally obtain an O(n log n) algorithm, which, in spite of being very simple, improves the best known complexity.
Fabien Viger Matthieu Latapy
LIP6, University Pierre and Marie Curie, 4 place Jussieu, 75005 Paris LIAFA, University Denis Didero LIAFA, University Denis Diderot, 2 place Jussieu, 75005 Paris
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
440-449
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）