New answers tagged

1 vote

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
0 votes

A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
Neal Young's user avatar
  • 10.1k
0 votes

property of minimal triangulations

I often wondered about this question so I appreciate the comments and answers of Laakeri and Marko. I don't know if it helps anybody but as someone who is not an expert on minimal separators I ...
steven kelk's user avatar
3 votes

property of minimal triangulations

As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property. Based on the definitions: A subset $S \subseteq V$ is an $a, b$-separator of $G$ ...
Marko Lalovic's user avatar

Top 50 recent answers are included