Hiya dudes,

can anyone tell me an algorithm for computing
minimum edge cover of bipartite graph?

Can anyone tell me a web site which includes
advanced algorithms (graph algorithms prefered :))
By the way, the site may be in Russian too.

Petko Minkov

I think this should work:
Find the maximum cardinality matching then for every
exposed vertex add one (doesn't matter which) edge
incident to the vertex.

> I think this should work:
> Find the maximum cardinality matching then for every
> exposed vertex add one (doesn't matter which) edge
> incident to the vertex.

hm, hm, interesting. i should check if it works
properly later on.

> I think this should work:
> Find the maximum cardinality matching then for every
> exposed vertex add one (doesn't matter which) edge
> incident to the vertex.

Is there difference between maximum bipartite matching
and maximum cardinality bipartite matching?

Ok, if every vertex is incident to matched edge then
which are the exposed vertices ?

> > I think this should work:
> > Find the maximum cardinality matching then for every
> > exposed vertex add one (doesn't matter which) edge
> > incident to the vertex.
>
> Is there difference between maximum bipartite matching
> and maximum cardinality bipartite matching?
>
> Ok, if every vertex is incident to matched edge then
> which are the exposed vertices ?
>
>

Maximum cardinality matching is weighted matching where
each edge weights 1.There is no difference but if the graph
is not bipartite finding the matching is very hard to code
(it involves finding augmentation paths and there is
shrinking of vertices and edges into new vertices).Finding
the matching on bipartite graph is easy(max flow).
Now for the second question if every vertex is matched then
don't add more edges.(the best thing you can do with each
covered edge is to cover 2 vertices).
Here is the algorithm again :
1) Find the matching on the bipartite graph with flow;
2) For every vertex if it isn't matched cover it with
random edge incident to the vertex.
This should work even on graphs that aren't bipartite but
as I said finding the matching is complicated.The
correctness of algorithm comes from the fact that there
aren't any incident exposed vertices, so once you find the
matching the best think you can do is cover each exposed
vertex with one edge.

1. About maximum matching. As you surely know matching
can be found also with alternating chains algorithm,
but not with network flow. I think this algorithmmaximum
matching. .. hm, may be it's my mistake.
But i think edge cover is a subset of graph edges
is working for general graphs!!

2. Minimum edge cover can contain less edges then

sets. So every edge which is not in this subset
is incident to an edge in this edge.

Hmm, so to be more clear - the source of my problem is
the second task from the last FMI-Open contest.
I still don't know how to solve it in polynomial
time. So i think this problem is minimum edge cover
in bip. graph.

I can't understand what you are trying to say at all.What
sets are you talking about?Yes the edge cover is subset of
all edges and yes you can use the standard matching
algorithm and you won't have to shrink vertices and edges
on graphs that are bipartite(you talk about the algorithm
that generates alternating trees do you?).Also I am sure
that the second task can't be solved with edge cover.I
highly doubt that there is polinomial algorithm for it I
think they wanted people to write heuristics.And I like to
use flows.

No, i'm not talking about alternating trees, i've
read some algorithms for finding matching with such
trees and some hungarian stuff ... i don't remember it.
this was really hard. i'm talking about finding
alternating path, and making XOR of the current matching
using this path, which infact is more complicated then
flow :).

i didn't participated in the last FMI, so i'll see if
you have full points probably the algorithm really is
not polytime.

> I can't understand what you are trying to say at all.What
> sets are you talking about?Yes the edge cover is subset
of
> all edges and yes you can use the standard matching
> algorithm and you won't have to shrink vertices and edges
> on graphs that are bipartite(you talk about the algorithm
> that generates alternating trees do you?).Also I am sure
> that the second task can't be solved with edge cover.I
> highly doubt that there is polinomial algorithm for it I
> think they wanted people to write heuristics.And I like
to
> use flows.