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