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 sub-graphs? Most of the previous work has focussed 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?
