Colorful Triangle Counting and a MapReduce Implementation

Rasmus Pagh

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

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
OriginalsprogEngelsk
TidsskriftInformation Processing Letters
Vol/bind112
Udgave nummer7
Sider (fra-til)277-281
ISSN0020-0190
StatusUdgivet - 2012

Emneord

  • Graph algorithms
  • Randomized algorithms
  • Concentration of measure
  • Parallel algorithms

Fingeraftryk

Dyk ned i forskningsemnerne om 'Colorful Triangle Counting and a MapReduce Implementation'. Sammen danner de et unikt fingeraftryk.

Citationsformater