Linear Time Algorithms for Generalized Edge Dominating Set Problems

Linear Time Algorithms for Generalized Edge Dominating Set Problems

0.00 Avg rating0 Votes
Article ID: iaor20119085
Volume: 50
Issue: 2
Start Page Number: 244
End Page Number: 254
Publication Date: Feb 2008
Journal: Algorithmica
Authors: ,
Keywords: minimum spanning tree
Abstract:

We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b e times for all eE, admits a linear time 2‐approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b e ∈{0,1} for all eE. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.

Reviews

Required fields are marked *. Your email address will not be published.