Visa en n-vertex, m-kantig oriktad graf som ett elektriskt nätverk med enhetsmotstånd som kanter. Vi utökar kända relationer mellan slumpmässiga promenader och elektriska nätverk genom att visa att motstånd i detta nätverk är intimt ansluten med längderna av slumpmässiga promenader på grafen. Till exempel, pendla tiden mellan två hörn s och t (den förväntade längden av en slumpmässig promenad från s till t och tillbaka) är exakt kännetecknas av den effektiva motståndet Rst mellan s och t: pendla tiden = 2mRst. Som en följd av detta kännetecknas täcktiden (den förväntade längden på en slumpmässig promenad som besöker alla hörn) av det maximala motståndet R i grafen till inom en faktor för log n: mR <_ cover time <_ O(mRlogn). För många grafer är de gränser på täcktiden som erhålls på detta sätt bättre än de som erhållits från tidigare tekniker, såsom adjacensmatrisens eigenvärden. I synnerhet förbättrar vi kända gränser för täckningstider för höggradiga grafer och expanders, och ger nya bevis på kända resultat för flerdimensionella maskor. Dessutom tycks motståndet ge en intuitivt tilltalande och lättfattlig inställning till dessa problem.
Anslutningar mellan slumpmässiga gångtider och elektriska motståndsnät beskrevs i REF.
The electrical resistance of a graph captures its commute and cover times
{'venue': 'computational complexity', 'journal': 'computational complexity', 'mag_field_of_study': ['Computer Science', 'Mathematics']}