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...") |
|||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur06 | |
| − | | | + | |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? |
| + | |||
| + | == 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].
