Målet med mötesplatsen i en graf är att möta två mobila agenter på någon nod av en okänd anonym ansluten graf. I den här artikeln fokuserar vi på möte i träd, och i likhet med de insatser som har gjorts för att lösa prospekteringsproblemet med kompakt automata, studerar vi storleken på minnet av mobila agenter som gör det möjligt att lösa mötesproblemet deterministiskt. Vi antar att agenterna är identiska och går i synkrona rundor. Vi visar först att om fördröjningen mellan starttiderna för agenterna är godtycklig, då den lägre gräns för minne som krävs för mötesplatsen är (log n) bitar, även för raden av längd n. Denna nedre gräns uppfyller en tidigare känd övre gräns för O (log n) bitar för mötesplats i godtyckliga diagram av storlek som mest n. Vårt huvudsakliga resultat är ett bevis på att mängden minne som behövs för möte med samtidig start beror i huvudsak på antalet blad av trädet, och är exponentiellt mindre påverkas av antalet n noder. Faktum är att vi presenterar två identiska agenter med O(log + log log n) bitar av minne som löser mötesplats problem i alla träd med som mest n noder och som mest blad. Därför, för klassen av träd med polylogaritmiskt många blad, det finns en exponentiell lucka i minsta minnesstorlek som behövs för mötet mellan scenariot med godtycklig fördröjning och scenariot med fördröjning noll. Dessutom visar vi att vår övre gräns är optimal genom att bevisa att (log + log log n) bitar av minne krävs för mötesplats, även i klassen av träd med grader som begränsas av 3.
Det var 1 Ett resultat från REF innebär att möte med samtidig start från godtyckliga icke-symmetriska initiala positioner i en n-node linje är möjligt med O (log log n) bitar av minne.
Delays Induce an Exponential Memory Gap for Rendezvous in Trees
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}