Talk:Edge cover
Appearance
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
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).
- 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)
Categories:
- Start-Class vital articles
- Wikipedia level-5 vital articles
- Wikipedia vital articles in Mathematics
- Start-Class level-5 vital articles
- Wikipedia level-5 vital articles in Mathematics
- Start-Class vital articles in Mathematics
- Start-Class mathematics articles
- Low-priority mathematics articles
- Start-Class Computer science articles
- Mid-importance Computer science articles
- WikiProject Computer science articles