The Library
A second look at counting triangles in graph streams (corrected)
Tools
Cormode, Graham and Jowhari, Hossein (2017) A second look at counting triangles in graph streams (corrected). Theoretical Computer Science, 683 . pp. 22-30. doi:10.1016/j.tcs.2016.06.020 ISSN 0304-3975.
|
PDF
WRAP-second-look-counting-triangles-graph-streams-Cormode-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (583Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2016.06.020
Abstract
In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O((m)/(ε4.5sqrt(T))) space and outputs a (1+ε) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman, Ostrovsky and Vilenchik, ICALP 2013, which distinguishes between triangle-free graphs and graphs with at least T triangle using O((m)/(T1/3)) space. Also, in terms of dependence on T, we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O((m)/(T1/2+ρ)) space for any constant ρ>=0.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Online social networks -- Mathematical models, Electronic mail systems -- Mathematical models | ||||||||
Journal or Publication Title: | Theoretical Computer Science | ||||||||
Publisher: | Elsevier Science BV | ||||||||
ISSN: | 0304-3975 | ||||||||
Official Date: | 30 June 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 683 | ||||||||
Page Range: | pp. 22-30 | ||||||||
DOI: | 10.1016/j.tcs.2016.06.020 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 11 January 2018 | ||||||||
Date of first compliant Open Access: | 11 January 2018 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year