Talk:Edge cover

Latest comment: 14 years ago by Miym in topic Greedy Algorithm

Greedy Algorithm

edit

Can I get a citation for the greedy algorithm? I think it's not correct. Suppose a graph with four nodes V = {a,b,c,d} that form a line, i.e. E = {(a,b),(b,c),(c,d)}. Choosing (b,c) forms a maximal matching, but there is no way to greedily extend it to a minimal edge cover (that is {(a,b),(c,d)} in this graph). I googled around a bit but found nothing relevant. --134.96.156.86 (talk)

Never mind. I always get maximAL and maximUM matchings confused. --134.96.156.86 (talk) —Preceding undated comment added 11:40, 21 December 2009 (UTC).Reply
Right. Regarding citations, e.g. in [1] you can find the theorem "the size of the minimum edge cover plus the size of the maximum number of independent edges equals the number of vertices of a graph"; note that "independent edges" = "matching". An easy way to prove this theorem is to consider the simple algorithm that greedily extends a maximum matching; once you have established the correctness of the algorithm, this theorem follows as a simple corollary (and vice versa). I think we could discuss this connection in more detail on this page. — Miym (talk) 17:54, 21 December 2009 (UTC)Reply