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:
“So God stepped over to the edge of the world
And He spat out the seven seas;
He batted His eyes, and the lightnings flashed;
He clapped His hands, and the thunders rolled;
And the waters above the earth came down,
The cooling waters came down.”
—James Weldon Johnson (1871–1938)
“You may call a jay a bird. Well, so he is, in a measure—because he’s got feathers on him, and don’t belong to no church, perhaps; but otherwise he is just as much a human as you be. And I’ll tell you for why. A jay’s gifts and instincts, and feelings, and interests, cover the whole ground. A jay hasn’t got any more principle than a Congressman.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)