[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:45:09 +0300

OK, thanks, got it. --M

On Fri, Apr 20, 2012 at 1:42 PM, Tamas Nepusz <address@hidden> wrote:
>> OK but I didn't get which is exactly the igraph function?
> There is no maximum matching function in igraph (in the 0.5 branch, at
> least), so you won't find it. igraph 0.6 will have maximum matching
> routines, but note that you don't want a maximum matching in your case,
> since the maximum matching and the maximal matching are not the same. A
> maximal matching is one that you cannot extend any more by adding more
> edges, while a maximum matching is a maximal matching with the _largest_
> possible number of edges. So, if you approximate a minimum edge dominating
> set with a maximum matching, you can potentially get a worse approximation
> than approximating it with a maximal matching (which is not necessarily
> maximum, so it can contain a smaller number of edges, so it can be closer to
> a minimum edge dominating set).
> --
> T.
> _______________________________________________
> 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]