All Questions
Tagged with max-cut np-complete
1 question
3
votes
1
answer
113
views
Deciding if max-cut with negative edge weights has a solution with positive value
I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value:
Given a graph $G=(V, E)$ and edge weights $w: E \...
- 187