Abstrakt. Två mobila agenter med distinkta identifierare och lokaliserade i noder av en okänd anonym ansluten graf, måste mötas på någon nod av grafen. Vi söker snabba deterministiska algoritmer för detta mötesproblem, under två scenarier: samtidig start, när båda agenterna börjar utföra algoritmen samtidigt, och godtycklig start, när starttiderna för agenterna godtyckligt bestäms av en motståndare. Mätningen av prestanda för en mötesplatsalgoritm är dess kostnad: för en given initial placering av agenter i en graf, är detta antalet steg sedan starten av den senare agenten tills mötesplatsen uppnås. Vi visar först att mötesplatsen kan slutföras till priset O(n + log l) på alla n-node träd, där l är den mindre av de två identifierarna, även med godtycklig start. Denna komplexitet i kostnaderna kan inte förbättras för vissa träd, inte ens vid samtidig start. Effektivt möte i träd bygger på snabb nätverksprospektering och kan inte användas när grafen innehåller cykler. Vi studerar vidare det enklaste nätverket, d.v.s. ringen. Vi bevisar att, med samtidig start, optimal kostnad för mötesplats på varje ring är (D log l), där D är det ursprungliga avståndet mellan agenter. Vi fastställer också gränser för möteskostnader i ringar med godtycklig start. För godtyckliga uppkopplade grafer är vårt huvudbidrag en deterministisk mötesplatssalgoritm med kostnadspolynom i n, τ och log l, där τ är skillnaden mellan starttiderna för agenterna. Vi visar också en lägre gräns (n 2 ) på kostnaden för mötesplats i vissa familj av grafer. Om samtidig start antas, vi konstruera en generisk mötesplats algoritm, arbetar för alla anslutna grafer, vilket är optimalt för klassen av grafer av begränsad grad, om det initiala avståndet mellan agenter begränsas.
Dessmark m.fl. REF föreslog en algoritm som inser att samla in Õ(n 5 ε τ l + n 10 l) enhet gånger för någon graf, där n är antalet noder, l är längden på den minsta ID av agenser, och τ är den maximala skillnaden mellan aktiveringstiderna för två agenser.
Deterministic Rendezvous in Graphs
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}