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:
“The stroke of the whip maketh marks in the flesh: but the stroke of the tongue breaketh the bones. Many have fallen by the edge of the sword: but not so many as have fallen by the tongue.”
—Ecclesiasticus Apocrypha. Ecclesiasticus, 28:17-8.
“I wouldn’t pray just for a old man that’s dead because he’s all right. If I was to pray, I’d pray for the folks that’s alive and don’t know which way to turn. Grampa here, he ain’t got no more trouble like that. He’s got his job all cut out for him. So cover him up and let him get to it.”
—Nunnally Johnson (1897–1977)