پوشش مجموعه ای - مرجع: motwani
يكشنبه, ۲۰ بهمن ۱۳۹۲، ۰۲:۴۲ ب.ظ
یک ابرگراف فرض کنید که هر راس آن یکی از مجموعه ها است (هزینه ی آن مجموعه) و هر یال یک عضو از مجموعه مرجع است که می تواند در چندین راس وجود داشته باشد.
الگوریتم: هر بار راس با بیشترین درجه را بردارید و همه ی یالهای متصل به آن را حذف کنید.
