Near-optimal Distributed Triangle Enumeration via Expander Decompositions

DOI10.1145/3446330MaRDI QIDQ5056410zbMATH OpenOpenAlexWikidataFDO

Authors Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, Hengjie Zhang

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3446330

zbMATH Keywords

CONGESTdistributed graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Distributed triangle detection via expander decomposition
• Triangle Finding and Listing in CONGEST Networks
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Expander decomposition and pruning: faster, stronger, and simpler

Cited in

(12)

• A note on improved results for one round distributed clique listing
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Distributed triangle detection via expander decomposition
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Deterministic near-optimal distributed listing of cliques
• On the streaming complexity of expander decomposition
• Fast approximate counting of cycles
• Brief announcement: Low-distortion clustering in bounded growth graphs
• Deterministic expander routing: faster and more versatile
• Computing minimum weight cycle in the CONGEST model
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Efficient distributed decomposition and routing algorithms in minor-free networks and their applications

This page was built for publication: Near-optimal Distributed Triangle Enumeration via Expander Decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056410)