Random generation of tournaments and asymmetric graphs with given out-degrees

详细信息    查看全文

• 作者：Charon ; Irè ; ne ; Germa ; Anne ; Hudry ; Olivier
• 关键词：Graph theory ; Random algorithms ; Tournaments ; Asymmetric graphs ; Out-degrees
• 刊名：European Journal of Operational Research
• 出版年：1996
• 出版时间：December 6, 1996
• 年：1996
• 卷：95
• 期：2
• 页码：411-419
• 全文大小：639 K

文摘

In this paper, we first present a polynomial algorithm which computes a random tournament with given out-degrees; any tournament having these out-degrees has a nonzero probability to be computed. Then we give a necessary and sufficient condition for a sequence of numbers to be the out-degrees (or similarly the in-degrees) of an asymmetric graph. Lastly, using the above algorithm and this characterization, we design a second polynomial algorithm to compute a random asymmetric graph with given out-degrees, and any asymmetric graph with these out-degrees has a nonzero probability to be found.