Re: [igraph] edge domination in igraph?

[Tamas Nepusz]

> 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.