# Difference between revisions of "Open Problems:11"

Line 6: | Line 6: | ||

== Update == | == 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].