محاسبه میانگین درجه رنگی گراف‌ها در زمان زیرخطی
الموضوعات :
محمدعلی آبام
1
( دانشگاه صنعتی شریف)
محمدرضا بهرامی
2
(دانشگاه صنعتی شریف)
الکلمات المفتاحية: الگوریتم‌های زمان- زیرخطی, الگوریتم‌های تقریبی, الگوریتم‌های گراف, درجه رنگی, میانگین درجه,
ملخص المقالة :
گراف‌ها یکی از ساختارهای مهم و پرکاربرد در ذخیره‌سازی داده‌ها هستند. برخی اوقات رئوس گراف‌ها دربردارنده ویژگی‌هایی است که محاسبه میزان اثر آنها بر روی گراف از اهمیت بسزایی برخوردار است. در این نوشتار برخی از این ویژگی‌ها را به کمک رنگ‌ها و درجه رنگی مدل کرده و حل بسیار سریع مسئله را به کمک دو الگوریتم زیرخطی که نیازی به مشاهده همه اطلاعات ندارد، مورد بررسی قرار می‌دهیم. در روش اول فرض می‌کنیم اطلاعات هر رأس از گراف و ویژگی‌های آن را می‌دانیم و سپس یک الگوریتم تقریبی با ضریب به ازای داده‌شده برای آن ارائه می‌دهیم. سپس در بخش بعدی این فرض را کنار گذاشته و نشان می‌دهیم همچنان می‌توان به چنین تقریبی دست یافت در حالی که امید ریاضی زمان اجرای الگوریتم ارائه‌شده زیرخطی است.
[1] R. Rubinfeld and A. Shapira, "Sublinear time algorithms," SIAM J. on Discrete Mathematics, vol. 25, no. 4, pp. 1562-15882011.
[2] A. Dasgupta, R. Kumar, and T. Sarlos, "On estimating the average degree," in Proc. 23rd Int. Conf. on World Wide Web, WWW’14, pp. 795-806, Seoul, South Korea, 7-11 Apr. 2014.
[3] O. Goldreich, "Introduction to testing graph properties," Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pp. 470-506, 2011.
[4] O. Goldreich and D. Ron, "Approximating average parameters of graphs," Random Structures and Algorithms, vol. 32, no. 4, pp. 473-493, 2008.
[5] O. Goldreich and D. Ron, "Estimating simple graph parameters in sublinear time," Encyclopedia of Algorithms, pp. 650-653, 2016.
[6] R. Canetti, G. Even, and O. Goldreich, "Lower bounds for sampling algorithms for estimating the average," Information Processing Letters, vol. 53, no. 1, pp. 17-25, 13 Jan. 1995.
[7] R. Motwani, R. Panigrahy, and Y. Xu, "Estimating sum by weighted sampling," in Proc. Int. Colloquium on Automata, Languages, and Programming, ICALP’07, pp. 53-64, Wroclaw, Poland, 9-13 Jul. 2007.
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
[9] U. Feige, "On sums of independent random variables with unbounded variance and estimating the average degree in a graph," SIAM J. on Computing, vol. 35, no. 4, pp. 964-984, 2006.
[10] T. Kaufman, M. Krivelevich, and D. Ron, "Tight bounds for testing bipartiteness in general graphs," SIAM J. on Computing, vol. 33, no. 6, pp. 1441-1483, 2004.
[11] O. Goldreich and D. Ron, "On estimating the average degree of a graph," Electronic Colloquium on Computational Complexity, vol. 11, Article 13, 9 pp., 2004.
