Colorful Triangle Counting and a MapReduce Implementation

Rasmus Pagh

Colorful Triangle Counting and a MapReduce Implementation

Rasmus Pagh

Algorithms

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer 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

Originalsprog	Engelsk
Tidsskrift	Information Processing Letters
Vol/bind	112
Udgave nummer	7
Sider (fra-til)	277-281
ISSN	0020-0190
Status	Udgivet - 2012

Emneord

Graph algorithms
Randomized algorithms
Concentration of measure
Parallel algorithms

Citationsformater

@article{e400c36e0bc44f23ace4ba2c2780ee01,

title = "Colorful Triangle Counting and a MapReduce Implementation",

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",

keywords = "Graph algorithms, Randomized algorithms, Concentration of measure, Parallel algorithms, Graph algorithms, Randomized algorithms, Concentration of measure, Parallel algorithms",

author = "Rasmus Pagh",

year = "2012",

language = "English",

volume = "112",

pages = "277--281",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Colorful Triangle Counting and a MapReduce Implementation

AU - Pagh, Rasmus

PY - 2012

Y1 - 2012

N2 - 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

AB - 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

KW - Graph algorithms

KW - Randomized algorithms

KW - Concentration of measure

KW - Parallel algorithms

KW - Graph algorithms

KW - Randomized algorithms

KW - Concentration of measure

KW - Parallel algorithms

M3 - Journal article

SN - 0020-0190

VL - 112

SP - 277

EP - 281

JO - Information Processing Letters

JF - Information Processing Letters

IS - 7

ER -

Colorful Triangle Counting and a MapReduce Implementation

Abstract

Emneord

Fingeraftryk

Citationsformater