[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] edge domination in igraph?
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] edge domination in igraph? |
Date: |
Fri, 20 Apr 2012 12:26:25 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:11.0) Gecko/20120329 Thunderbird/11.0.1 |
Hi,
> I know that finding a minimum edge dominating set is an NP-hard
> problem. However, I was wondering whether there is an approximation
> algorithm which is implemented in igraph.
A pretty easy approximation algorithm with a multiplicative factor of 2 is
as follows: find _any_ maximal matching. That's pretty easy; take an
unmatched vertex, check whether it has an unmatched neighbor, and if so,
assign them to each other. Repeat until finished. Otherwise I am not aware
of any algorithm in igraph that can be used for approximating a minimum edge
dominating set.
Best,
Tamas