"Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting

Details "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting

2012-01-31

arxiv.org/abs/1201.6652v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Let G=(V,E) be an n-vertex graph and M_d a d-vertex graph, for some constant d. Is M_d a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to O(log n) bits. A simple deterministic algorithm that requires O(n^((d-2)/d)/log n) communication rounds is presented. For the special case that M_d is a triangle, we present a probabilistic algorithm that requires an expected O(n^(1/3)/(t^(2/3)+1)) rounds of communication, where t is the number of triangles in the graph, and O(min{n^(1/3)*log^(2/3)n/(t^(2/3)+1),n^(1/3)}) with high probability. We also present an arboricity-based algorithm, specially suited for sparse graphs, featuring a round complexity of O((A^2\log_(2+n/A^2) n)/n) \subset O(|E|/n+log n), where A denotes the arboricity of G.

Affiliated with

Also associated with

No associations

Rating

"Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57683