Difference between revisions of "Open Problems:11"
((typo fix) focussed -> focused) |
|||
| Line 4: | Line 4: | ||
|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 | + | 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 02:03, 18 February 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?
