Rotorroutermekanismen infördes som ett deterministiskt alternativ till den slumpmässiga vandringen i oriktade grafer. I denna modell, en uppsättning k identiska vandrare är utplacerad parallellt, med början från en vald delmängd av noder, och rör sig runt grafen i synkrona steg. Under processen upprätthåller varje nod en cyklisk ordning av sina utgående bågar, och propagerar successivt vandrare som besöker den längs sina utgående bågar i round-robin mode, enligt den fasta beställningen. Vi betraktar skyddstiden för ett sådant system, dvs. antalet steg varefter varje nod har besökts av minst en promenad, oavsett startplatserna för promenaderna. I fråga om k = 1, Yanovski et al. (2003) och visade att en enda gång uppnår en cover time av exakt  till (mD) för n-node graf med m kanter och diameter D, och att gångaren så småningom stabiliseras till en traversal av en eulerian krets på uppsättningen av alla riktade kanter av grafen. För k > 1 parallella promenader kan inget liknande strukturellt beteende observeras. I detta arbete ger vi snäva gränser på omslaget tiden av k parallella rotor promenader i en graf. Vi visar att denna cover-tid är som mest (mD/ log k) och minst (mD/ k) för vilken graf som helst, vilket motsvarar en upphastighet på mellan (log k) och (k) med avseende på cover-tiden för en enda gång. Båda dessa extremvärden för upphastighet uppnås för vissa grafklasser. Våra resultat håller för upp till ett polynomiskt stort antal promenader, k = O(poly(n)).
I REF, Dereniowski m.fl. fastställa gränser för minsta och största möjliga täckningstid för en i värsta fall initiering av ett k- rotor- routersystem i en graf G med m- kanter och diameter D, som mD/ k respektive O(mD/ log k).
Bounds on the cover time of parallel rotor walks
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}