Re: [igraph] edge domination in igraph?

[Moses Boudourides]

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