Kényszerfeltételeket teljesítő fokszámsorozatok realizációinak mintavételezése (Fast sampling from graphical realizations of restricted degree sequences)

Miklós István előadásának absztraktja

(Erdős Péterrel, Soukup Lajossal, Toroczkai Zoltánnal és Kiss Zoltánnal közös munka.)

2013. október 24. csütörtök, 16:15

 
 

Egy fokszámsorozat realizációi azok a gráfok, amelyek fokai megegyeznek az adott fokszámsorozattal. Ezek közül lehet tekinteni azt a részhalmazt, amelyekben levő gráfok bizonyos kényszerfeltételeknek is eleget tesznek, például nem tartalmaznak valamilyen kizárt gráfot, a különböző fokú pontok közötti összélszám adott, stb. Az előadáson ezek közül olyan eseteket ismertetünk, amelyekre a megoldások közel egyenletes eloszlásából lehet mintavételezni gyorsan keveredő Markov láncok segítségével.
A bemutatott munka közös Erdős Péterrel, Soukup Lajossal, Toroczkai Zoltánnal és Kiss Zoltánnal, és az alábbi két kéziraton alapul:
http://arxiv.org/abs/1301.7523
http://arxiv.org/abs/1307.5295


 
Tóth Imre Péter, 2013.10.17