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

DOI10.1007/978-3-642-33651-5_14MaRDI QIDQ4909412zbMATH OpenOpenAlexFDO

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

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) 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

(29)

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

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)