“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting

DOI10.1007/978-3-642-33651-5_14zbMath1377.68316OpenAlexW1845051857MaRDI QIDQ4909412

Shir Peled, Christoph Lenzen, Danny Dolev

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-33651-5_14

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distributed algorithms (68W15)

Related Items (20)

Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Lessons from the congested clique applied to MapReduce ⋮ Fault-tolerant graph realizations in the congested clique ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Algebraic methods in the congested clique ⋮ Reliable communication over highly connected noisy networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Fast approximate shortest paths in the congested clique ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Near-optimal scheduling in the congested clique

This page was built for publication: “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting