مرکز منطقه ای اطلاع رسانی علوم و فناوری فصلنامه مهندسی برق و مهندسی کامپيوتر ايران 16823745 19 2 2021 11 17 Computing Colored Average Degree of Graphs in Sublinear Time محاسبه میانگین درجه رنگی گراف‌ها در زمان زیرخطی 143 148 fa محمدعلی آبام دانشكده مهندسي كامپيوتر محمدرضا بهرامی دانشكده مهندسي كامپيوتر 2020 3 12 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. گراف‌ها یکی از ساختارهای مهم و پرکاربرد در ذخیره‌سازی داده‌ها هستند. برخی اوقات رئوس گراف‌ها دربردارنده ویژگی‌هایی است که محاسبه میزان اثر آنها بر روی گراف از اهمیت بسزایی برخوردار است. در این نوشتار برخی از این ویژگی‌ها را به کمک رنگ‌ها و درجه رنگی مدل کرده و حل بسیار سریع مسئله را به کمک دو الگوریتم زیرخطی که نیازی به مشاهده همه اطلاعات ندارد، مورد بررسی قرار می‌دهیم. در روش اول فرض می‌کنیم اطلاعات هر رأس از گراف و ویژگی‌های آن را می‌دانیم و سپس یک الگوریتم تقریبی با ضریب به ازای داده‌شده برای آن ارائه می‌دهیم. سپس در بخش بعدی این فرض را کنار گذاشته و نشان می‌دهیم همچنان می‌توان به چنین تقریبی دست یافت در حالی که امید ریاضی زمان اجرای الگوریتم ارائه‌شده زیرخطی است. http://ijece.org/ar/Article/Download/28837