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