Skip to main content
Share Your Experience: Take the 2024 Developer Survey
4 votes

Minimum number of triangles required to cover a complete graph?

This problem is the subject of (and was completely solved in) the paper "M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, ...
Nathaniel Johnston's user avatar
2 votes
Accepted

Enumerating all Vertex Covers of Size at most $k$

The algorithm fails in the case, when there are no edges left to cover, because then it does not have a structure to branch on. Consider for example the case where the graph is edgeless, then we have $...
Christian Komusiewicz's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible