کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4952056 1442006 2017 9 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
A second look at counting triangles in graph streams (corrected)
ترجمه فارسی عنوان
نگاه دوم به مثلث شمارش در جریان گراف (اصلاح شده)
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O(mε2.5Tpolylog(m)) space and outputs a (1+ε) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman, Ostrovsky and Vilenchik, ICALP 2013, which distinguishes between triangle-free graphs and graphs with at least T triangle using O(mT1/3) space. Also, in terms of dependence on T, we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O(mT1/2+ρ) space for any constant ρ≥0.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 683, 30 June 2017, Pages 22-30
نویسندگان
, ,