In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
Read more about Edge Cover: Definition, Algorithms
Famous quotes containing the words edge and/or cover:
“A lonely man is a lonesome thing, a stone, a bone, a stick, a receptacle for Gilbey’s gin, a stooped figure sitting at the edge of a hotel bed, heaving copious sighs like the autumn wind.”
—John Cheever (1912–1982)
“If I use the media, even with tricks, to publicise a black youth being shot in the back in Teaneck, New Jersey ... then I should be praised for it, and it’s more of a comment on them than me that it would take tricks to make them cover the loss of life.”
—Al, Rev. Sharpton (b. 1954)