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- More
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.
Manuscript profile
Rimag
Rimag is an integrated platform to accomplish all scientific journal requirements such as submission, evaluation, reviewing, editing, DOI assignment and publishing in the web.