Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Max Cut #7291

Closed
nathanncohen mannequin opened this issue Oct 25, 2009 · 6 comments
Closed

Max Cut #7291

nathanncohen mannequin opened this issue Oct 25, 2009 · 6 comments
Assignees
@rlmill
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-4.3

Comments

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Oct 25, 2009

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
@nathanncohen nathanncohen mannequin added this to the sage-4.3.1 milestone Oct 25, 2009
@nathanncohen nathanncohen mannequin assigned rlmill Oct 25, 2009
@nathanncohen nathanncohen mannequin added the s: needs review label Dec 14, 2009
@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 15, 2009

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?

@rlmill rlmill mannequin added s: needs work and removed s: needs review labels Dec 15, 2009
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 16, 2009

comment:3

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

Updated !

@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Dec 16, 2009

Attachment: trac_7291.patch.gz

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Reviewer: Robert Miller

@rlmill
Copy link
Mannequin

rlmill mannequin commented Dec 16, 2009

Author: Nathann Cohen

@mwhansen
Copy link
Contributor

Merged: sage-4.3.rc1

@mwhansen mwhansen modified the milestones: sage-4.3.1, sage-4.3 Dec 19, 2009
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rlmill rlmill

Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-4.3
Development

No branches or pull requests
1 participant
@mwhansen