[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] edge domination in igraph?

From: Moses Boudourides
Subject: Re: [igraph] edge domination in igraph?
Date: Fri, 20 Apr 2012 13:39:58 +0300

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



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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]