Difference between revisions of "Open Problems:11"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
((typo fix) focussed -> focused)
m (updating header)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Counting Triangles
 
 
|source=kanpur06
 
|source=kanpur06
 
|who=Stefano Leonardi
 
|who=Stefano Leonardi
 
}}
 
}}
 
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?
 
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?

Revision as of 01:40, 7 March 2013

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?