Difference between revisions of "Open Problems:11"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (1 revision)
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 11: Counting Triangles}}
+
{{Header
{{Infobox
+
|source=kanpur06
|label1 = Proposed by
+
|who=Stefano Leonardi
|data1 = Stefano Leonardi
 
|label2 = Source
 
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
 
|label3 = Short link
 
|data3 = http://sublinear.info/11
 
 
}}
 
}}
Given a stream in which edges are inserted and deleted to/from an unweighted, undirected graph, how well can we count triangles and other sub-graphs? Most of the previous work has focussed on the case of insertions {{cite|BarYossefKS-02|JowhariG-05|BuriolFLMS-06}} although it appears that one of the algorithms in {{cite|JowhariG-05}} may work when edges can be deleted. Is it possible to match the insert-only bounds when edges are inserted and deleted?
+
Given a stream in which edges are inserted and deleted to/from an unweighted, undirected graph, how well can we count triangles and other sub-graphs? Most of the previous work has focused on the case of insertions {{cite|BarYossefKS-02|JowhariG-05|BuriolFLMS-06}} although it appears that one of the algorithms in {{cite|JowhariG-05}} may work when edges can be deleted. Is it possible to match the insert-only bounds when edges are inserted and deleted?
 +
 
 +
== Update ==
 +
Ahn, Guha, and McGregor {{cite|AhnGM-12b}} proposed an algorithm for streams with both insertions and deletions. It matches the best known bounds for insertion-only streaming algorithms {{cite|BuriolFLMS-06}}.

Latest revision as of 04:12, 28 April 2017

Suggested by Stefano Leonardi
Source Kanpur 2006
Short link https://sublinear.info/11

Given a stream in which edges are inserted and deleted to/from an unweighted, undirected graph, how well can we count triangles and other sub-graphs? Most of the previous work has focused on the case of insertions [BarYossefKS-02,JowhariG-05,BuriolFLMS-06] although it appears that one of the algorithms in [JowhariG-05] may work when edges can be deleted. Is it possible to match the insert-only bounds when edges are inserted and deleted?

Update[edit]

Ahn, Guha, and McGregor [AhnGM-12b] proposed an algorithm for streams with both insertions and deletions. It matches the best known bounds for insertion-only streaming algorithms [BuriolFLMS-06].