Max Cut

[nathanncohen]

Max cut is a NP-Hard problem, which could as usual be written as a LP if no better solution is found.

http://en.wikipedia.org/wiki/Maximum_cut

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7291

[rlmill]

comment:2

You should include more examples in your doctests. At least make sure that each input is tested. For example:

sage: g.max_cut(vertices=True)
30.0

Shouldn't this be returning two sets of vertices?

[nathanncohen]

comment:3

I had forgotten the implication : vertices=True => value_only=True :-)

Updated !

[nathanncohen]

Attachment: trac_7291.patch.gz

[rlmill]

Reviewer: Robert Miller

[rlmill]

Author: Nathann Cohen