Colorful triangle counting and a \textsc{MapReduce} implementation

DOI10.1016/j.ipl.2011.12.007zbMath1237.68245OpenAlexW2002205566MaRDI QIDQ413300

Charalampos E. Tsourakakis, Rasmus Pagh

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.12.007

zbMATH Keywords

parallel algorithmsgraph algorithmsconcentration of measurerandomized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (10)

Triangle counting in dynamic graph streams ⋮ A second look at counting triangles in graph streams (corrected) ⋮ Efficient Computation of the Weighted Clustering Coefficient ⋮ Distributed discovery of frequent subgraphs of a network using MapReduce ⋮ Approximately Counting Triangles in Sublinear Time ⋮ FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ A second look at counting triangles in graph streams ⋮ Clique Counting in MapReduce ⋮ Efficient computation of the Weighted Clustering Coefficient

Uses Software

• DOULION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Random generation of combinatorial structures from a uniform distribution
• A note on an inequality involving the normal distribution
• Triangle Sparsifiers
• Approximating Clustering Coefficient and Transitivity
• Divide and conquer martingales and the number of triangles in a random graph
• On the concentration of multivariate polynomials with small expectation
• The infamous upper tail
• Computing and Combinatorics
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
• Concentration of multivariate polynomials and its applications

This page was built for publication: Colorful triangle counting and a \textsc{MapReduce} implementation