Difference between revisions of "Open Problems:11"
(Created page with "{{DISPLAYTITLE:Problem 11: Counting Triangles}} {{Infobox label1 = Proposed by data1 = Stefano Leonardi label2 = Source data2 = Kanpur 2006 labe...") 
m (1 revision) 
(No difference)

Revision as of 05:33, 8 November 2012
Proposed by  Stefano Leonardi 

Source  Kanpur 2006 
Short link  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 subgraphs? Most of the previous work has focussed on the case of insertions [BarYossefKS02,JowhariG05,BuriolFLMS06] although it appears that one of the algorithms in [JowhariG05] may work when edges can be deleted. Is it possible to match the insertonly bounds when edges are inserted and deleted?