1403/01/10
احمد مرادی

احمد مرادی

مرتبه علمی: استادیار
ارکید:
تحصیلات: دکترای تخصصی
اسکاپوس:
دانشکده: دانشکده علوم ریاضی
نشانی:
تلفن: 01135302421

مشخصات پژوهش

عنوان
Vertex Cover: A new generalization
نوع پژوهش
Presentation
کلیدواژه‌ها
Vertex cover problem , Half integral property, Approximation Algorithm
سال
2016
پژوهشگران Ahmad Moradi

چکیده

Given a graph G=(V,E), a non-negative weight function c, and a subset of nodes, S. We consider a generalization of the vertex cover problem over G in which the objective is to find a vertex cover (if available) of minimum cost that does not use any node of S. We show that this generalization of vertex cover problem preserves half integrality property and thereby give a 2-optimal approximation algorithm.