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:
“Women were formed to temper Mankind, and sooth them into Tenderness and Compassion; not to set an Edge upon their Minds, and blow up in them those Passions which are too apt to rise of their own Accord.”
—Joseph Addison (1672–1719)
“Nothing can we call our own but death,
And that small model of the barren earth
Which serves as paste and cover to our bones.”
—William Shakespeare (1564–1616)