Triangle Finding and Listing in CONGEST Networks

DOI10.1145/3087801.3087811MaRDI QIDQ5368990zbMATH OpenOpenAlexFDO

Authors Taisuke Izumi, François Le Gall

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09061

zbMATH Keywords

congest modeldistributed algorithmsgraph algorithmstriangle findingtriangle listing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: Triangle-free graphs play a central role in graph theory, and triangle detection (or triangle finding) as well as triangle enumeration (triangle listing) play central roles in the field of graph algorithms. In distributed computing, algorithms with sublinear round complexity for triangle finding and listing have recently been developed in the powerful CONGEST clique model, where communication is allowed between any two nodes of the network. In this paper we present the first algorithms with sublinear complexity for triangle finding and triangle listing in the standard CONGEST model, where the communication topology is the same as the topology of the network. More precisely, we give randomized algorithms for triangle finding and listing with round complexity $O(n^{2/3}(logn{)}^{2/3})$ and $O(n^{3/4}logn)$, respectively, where $n$ denotes the number of nodes of the network. We also show a lower bound $Omega(n^{1/3}/logn)$ on the round complexity of triangle listing, which also holds for the CONGEST clique model.

Recommendations

• Experimental and Efficient Algorithms
• An efficient exact algorithm for triangle listing in large graphs
• Sparse matrix multiplication and triangle listing in the congested clique model
• Sparse matrix multiplication and triangle listing in the congested clique model
• iTri: index-based triangle listing in massive graphs
• Optimization of triangular networks with spatial constraints
• Enumerating triangulation paths
• Routing on Triangles, Tori and Honeycombs
• An efficient algorithm for enumeration of triangulations

Cited in

(24)

• Near-optimal scheduling in the congested clique
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• 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
• A note on improved results for one round distributed clique listing
• Deterministic subgraph detection in broadcast CONGEST
• Lower bounds for subgraph detection in the CONGEST model
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Detecting cliques in CONGEST networks
• Sparse matrix multiplication and triangle listing in the congested clique model
• Distributed detection of cliques in dynamic networks
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Distributed triangle detection via expander decomposition
• The communication complexity of set intersection and multiple equality testing
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Brief Announcement: What Can We Compute in a Single Round of the Congested Clique?
• Fast distributed algorithms for girth, cycles and small subgraphs
• Deterministic near-optimal distributed listing of cliques
• Fast approximate counting of cycles
• Deterministic expander routing: faster and more versatile
• Computing minimum weight cycle in the CONGEST model
• Distributed subgraph finding: progress and challenges (invited talk)

This page was built for publication: Triangle Finding and Listing in CONGEST Networks

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