Problem 11: Counting Triangles

From Open Problems in Sublinear Algorithms
Revision as of 02:03, 18 February 2013 by 71.58.69.223 (talk) ((typo fix) focussed -> focused)
Jump to: navigation, search
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?

Retrieved from "https://sublinear.info/index.php?title=Open_Problems:11&oldid=596"