Skip to search box Skip to navigation Skip to main content

Colorful Triangle Counting and a MapReduce Implementation

Rasmus Pagh

Algorithms

Research Output:

Journal Article or Conference Article in Journal

Journal article

Peer-review

Publication Information

Output type

Research Output:

Journal Article or Conference Article in Journal

Journal article

Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 277-281

Journal (Volume, Issue Number)

Information Processing Letters (Volume 112, Issue 7)

Publication milestones

Published - 2012

Publication status

Published - 2012

ISSN

0020-0190

Publication IDs

Scopus: 84855778834

Abstract

In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles

Publication metrics

PlumX

Citations

132

Captures

42