Distributed Triangle Detection via Expander Decomposition

DOI10.1137/1.9781611975482.51zbMath1431.68129arXiv1807.06624OpenAlexW2952895509MaRDI QIDQ5236234

Yi-Jun Chang, Hengjie Zhang, Seth Pettie

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.06624

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (10)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ A note on improved results for one round distributed clique listing ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast approximate shortest paths in the congested clique ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Near-optimal scheduling in the congested clique

This page was built for publication: Distributed Triangle Detection via Expander Decomposition