MINIMUM-WEIGHT VERTEX COVER PROBLEM FOR 2-CLASS RESOURCE CONNECTION GRAPHS

We study the minimum-weight vertex cover problem for a special type of three-partite graphs called two-class resource connection graphs. Thi s problem is important due to its various application in different pro blem domains, especially in broadcast distributed computing systems. A mapping between this problem and some practical problems is developed and it is shown that these problems are equivalent. We prove the mini mum-weight vertex cover problem for two-class resource connection grap hs is NP-hard. Some properties of such graphs are identified and an ef ficient heuristic based on the identified properties is given. Two int eresting special cases of this problem are also discussed.