Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
How Hard Is Counting Triangles in the Streaming Model?
verfasst von : Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The problem of (approximately) counting the number of triangles in a graph is one of the basic problems in graph theory. In this paper we study the problem in the streaming model. Specifically, the amount of memory required by a randomized algorithm to solve this problem. In case the algorithm is allowed one pass over the stream, we present a best possible lower bound of Ω(
m
) for graphs
G
with
m
edges. If a constant number of passes is allowed, we show a lower bound of Ω(
m
/
T
),
T
the number of triangles. We match, in some sense, this lower bound with a 2-pass
O
(
m
/
T
1/3
)-memory algorithm that solves the problem of distinguishing graphs with no triangles from graphs with at least
T
triangles. We present a new graph parameter
ρ
(
G
) – the triangle density, and conjecture that the space complexity of the triangles problem is Θ(
m
/
ρ
(
G
)). We match this by a second algorithm that solves the distinguishing problem using
O
(
m
/
ρ
(
G
))-memory.