``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

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

(29)

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