I detta papper ger vi ett uttryckligt sätt att beräkna asymptotiskt nästan säkra övre gränser på bisektionsbredden av slumpmässiga d-regelbundna grafer, för något värde av d. De övre gränserna erhålls från analysen av prestandan hos en randomiserad girig algoritm för att hitta bisektioner av d-regelbundna grafer. Vi tillhandahåller gränser för 5 ≤ d ≤ 12. Vi ger också empiriska värden av storleken på den bisektion som algoritmen hittat för några små värden av d och jämför den med numeriska approximationer av våra teoretiska gränser. Vår analys ger också asymptotiska nedre gränser för storleken på den maximala bisektion.
Diaz m.fl. REF ger nästan säkra övre gränser för bisektionsbredden av slumpmässigt genererade regelbundna grafer.
Bounds on the bisection width for random d -regular graphs
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}