Vi etablerar en gräns för den klassiska PUSH-PUL rykte sprider protokoll på godtyckliga grafer, i termer av vertex expansion av grafen. Vi visar att O(log 2 (n)/α) rundor räcker med hög sannolikhet för att sprida ett rykte från en enda nod till alla n noder, i någon graf med vertex expansion minst α. Denna gräns matchar den kända nedre gränsen, och avgör frågan om förhållandet mellan ryktet sprids och vertex expansion frågas av Chierichetti, Lattanzi, och Panconesi [7]. Dessutom kan några av de argument som används i beviset vara av oberoende intresse, eftersom de ger nya insikter, till exempel, om hur man väljer en liten uppsättning noder att plantera ryktet initialt, för att garantera snabba rykten sprider.
I synnerhet, och REF visade sig vara en O( log 2 n α ) bunden och visade att den var stram också.
Tight Bounds for Rumor Spreading with Vertex Expansion
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}