Computing Colored Average Degree of Graphs in Sublinear Time
Subject Areas : electrical and computer engineeringمحمدعلی آبام 1 , محمدرضا بهرامی 2
1 -
2 -
Keywords:
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.
