Computing Colored Average Degree of Graphs in Sublinear Time
Subject Areas : electrical and computer engineering
Mohammad Ali
Abam
1
محمدرضا
بهرامی
2
Keywords: Sublinear-time algorithms, approximation algorithms, graph algorithms, colored degree, average degree,
Abstract :
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.