New answers tagged

1 vote
Accepted

Is the ABC-partition problem NP-hard?

I did not find the proof claimed by Garey and Johnson at [SP16]. But I found two other proofs, which seem independent (do not rely on the existing proof): Yu, Hoogeveen and Lenstra (2004) Caracciolo, ...
Erel Segal-Halevi's user avatar
1 vote
Accepted

Covering a graph with M cliques maximizing total edges weight

One approach is to solve this with tools from operations research and combinatorial optimization, and specifically, to view this as an instance of ILP or SAT. Let $x_{c,i}$ be a variable that will be ...
D.W.'s user avatar
  • 158k

Top 50 recent answers are included