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
| Original language | English |
|---|---|
| Journal | Information Processing Letters |
| Volume | 112 |
| Issue number | 7 |
| Pages (from-to) | 277-281 |
| ISSN | 0020-0190 |
| Publication status | Published - 2012 |
Keywords
- Graph algorithms
- Randomized algorithms
- Concentration of measure
- Parallel algorithms