Opened 11 years ago

Closed 11 years ago

#7291 closed enhancement (fixed)

Max Cut

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_7291.patch​ (5.4 KB) - added by ncohen 11 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 11 years ago by ncohen

  • Report Upstream set to N/A
  • Status changed from new to needs_review

comment:2 Changed 11 years ago by rlm

  • Status changed from needs_review to needs_work

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?

comment:3 Changed 11 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Updated !

Changed 11 years ago by ncohen

comment:4 Changed 11 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:5 Changed 11 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Milestone changed from sage-4.3.1 to sage-4.3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.