``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)

DOI10.1007/978-3-642-33651-5_14MaRDI QIDQ4909412zbMATHOpenAlexFDO

Authors Danny Dolev, Christoph Lenzen, Shir Peled

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)

Recommendations

• Triangle Finding and Listing in CONGEST Networks
• Distributed triangle detection via expander decomposition
• Deterministic subgraph detection in broadcast CONGEST
• Approximately counting triangles in sublinear time
• On the power of the congested clique model

Cited in

(26)

• Detecting cliques in CONGEST networks
• Deterministic subgraph detection in broadcast CONGEST
• Lower bounds for subgraph detection in the CONGEST model
• Detecting cliques in CONGEST networks
• Sparse matrix multiplication and triangle listing in the congested clique model
• Deterministic near-optimal distributed listing of cliques
• Near-optimal scheduling in the congested clique
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• Large-scale distributed algorithms for facility location with outliers
• Distributed Discovery of Large Near-Cliques
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Fault-tolerant graph realizations in the congested clique
• The effect of range and bandwidth on the round complexity in the congested clique model
• Dynamic detection of subgraphs in computer networks
• Lessons from the congested clique applied to MapReduce
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed detection of cliques in dynamic networks
• Distributed triangle detection via expander decomposition
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Fast distributed algorithms for girth, cycles and small subgraphs
• Sparse matrix multiplication and triangle listing in the congested clique model
• Fast approximate shortest paths in the congested clique
• Derandomizing local distributed algorithms under bandwidth restrictions
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Reliable communication over highly connected noisy networks

This page was built for publication: ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)

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