Re: [igraph] edge domination in igraph?

[Moses Boudourides]

OK but I didn't get which is exactly the igraph function? In any case,
I've found a Python implementation:

http://jorisvr.nl/maximummatching.html

--M

On Fri, Apr 20, 2012 at 1:26 PM, Tamas Nepusz <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help