New Streaming Algorithms for Counting Triangles in Graphs

摘要：

We present three streaming algorithms that (∈,δ)-approximate the number of triangles in graphs. Similar to the previous algorithms 3, the space usage of presented algorithms are inversely proportional to the number of triangles while, for some families of graphs, the space usage is improved. We also prove a lower bound, based on the number of triangles, which indicates that our first algorithm behaves almost optimally on graphs with constant degrees.

作者: Hossein Jowhari Mohammad Ghodsi

作者单位: Computer Engineering Department Sharif University of Technology, Tehran, Iran

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 710-716

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）