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:
“And hiving wisdom with each studious year,
In meditation dwelt, with learning wrought,
And shaped his weapon with an edge severe,
Sapping a solemn creed with solemn sneer.”
—George Gordon Noel Byron (1788–1824)
“See, there is a place by me where you shall stand on the rock; and while my glory passes by I will put you in a cleft of the rock, and I will cover you with my hand until I have passed by;
then I will take away my hand, and you shall see my back; but my face shall not be seen.””
—Bible: Hebrew, Exodus 33:21-23.