محاسبه میانگین درجه رنگی گراف‌ها در زمان زیرخطی
محورهای موضوعی : مهندسی برق و کامپیوترمحمدعلی آبام 1 * , محمدرضا بهرامی 2
1 - دانشگاه صنعتی شریف
2 - دانشگاه صنعتی شریف
کلید واژه: الگوریتم‌های زمان- زیرخطی, الگوریتم‌های تقریبی, الگوریتم‌های گراف, درجه رنگی, میانگین درجه,
چکیده مقاله :
گراف‌ها یکی از ساختارهای مهم و پرکاربرد در ذخیره‌سازی داده‌ها هستند. برخی اوقات رئوس گراف‌ها دربردارنده ویژگی‌هایی است که محاسبه میزان اثر آنها بر روی گراف از اهمیت بسزایی برخوردار است. در این نوشتار برخی از این ویژگی‌ها را به کمک رنگ‌ها و درجه رنگی مدل کرده و حل بسیار سریع مسئله را به کمک دو الگوریتم زیرخطی که نیازی به مشاهده همه اطلاعات ندارد، مورد بررسی قرار می‌دهیم. در روش اول فرض می‌کنیم اطلاعات هر رأس از گراف و ویژگی‌های آن را می‌دانیم و سپس یک الگوریتم تقریبی با ضریب به ازای داده‌شده برای آن ارائه می‌دهیم. سپس در بخش بعدی این فرض را کنار گذاشته و نشان می‌دهیم همچنان می‌توان به چنین تقریبی دست یافت در حالی که امید ریاضی زمان اجرای الگوریتم ارائه‌شده زیرخطی است.
Graphs are common data structures which widely used for information storage and retrieval. Occasionally some vertices of a graph contain specific features or information, which we value in their effect. We consider modeling this effect formally, and we devise two super-fast algorithms to approximate the colored average degree. In the first method, we assume the information of each vertex is available; hence, the provided algorithm works with a 2+ϵ approximation factor. Eventually, we waive this assumption and find another algorithm with the same approximation factor, which computes the answer in the sublinear expected time.
[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.