Abstrakt. Vi presenterar enkla deterministiska algoritmer för subgraffynd och uppräkning i sändningen CONGEST modell för distribuerad beräkning: -För varje konstant k, detektera k-patter och träd på k noder kan göras i O(1) rundor. -För varje konstant k, detektera k-cykler och pseudoträd på k noder kan göras i O(n) rundor. -På d-degenererade grafer, klichéer och 4-cykler kan räknas upp i O(d + log n) rundor, och 5-cykler i O(d 2 + log n) rundor. I många fall är dessa gränser nära logaritmiska faktorer. Dessutom visar vi att algoritmerna för d-degenererade grafer kan förbättras till optimal komplexitet O(d/log n) respektive O(d 2 / log n), i den stödda CONGEST-modellen, som kan ses som en mellanmodell mellan CONGEST och den överbelastade klicken.
Nämligen, i REF visades det att upptäcka k-vägar och träd på k-nodes kan göras deterministiskt i O(k2 k ) rundor av sändande CONGEST modellen.
Deterministic subgraph detection in broadcast CONGEST
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}