# Difference between revisions of "Open Problems:11"

m (1 revision) |
|||

Line 1: | Line 1: | ||

− | {{ | + | {{Header |

− | + | |title=Counting Triangles | |

− | | | + | |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 focussed 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? | 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 {{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 05:05, 16 November 2012

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 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?