9
votes
Accepted
Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?
Yes, it has been solved.
In 1989 Borodin proved that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11, improving on Plummer's upper bound of 13. The 11 bound is tight [...
- 188k
1
vote
Accepted
Random Optimization on Graphs: Minimum Cut
As noted in the answer by Puck Rombach, the problem is NP-hard for fixed weights. However the OP asked about random IID weights. In this case finding the mincut or maxcut is still not known to be in P,...
- 14.2k
1
vote
Random Optimization on Graphs: Minimum Cut
Your problem is not in P in general. If you allow negative weights on edges, then you may have a graph where no edges have positive weight, in which case the problem of finding a min cut is equivalent ...
- 567
Only top scored, non community-wiki answers of a minimum length are eligible