#11944: Update Graph.clique_maximum to use MILP
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: tbd
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.3
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Coudert | Author: Nathann Cohen
Merged: | Dependencies: 11846, 11928
-----------------------------+----------------------------------------------
Changes (by ncohen):
* status: needs_info => needs_review
Comment:
Hello !!!
It would be, but not in this patch, as it does not do anything but asks
for the "independent set algorithm" to do it.
The answer, however is "YES", and much more :
I interfaced some time ago an external C code for modular decomposition.
With this decomposition, you obtain (given a graph) a recursive
decomposition into connected components and anticonnected components (the
complement of connectedcomponents). This is what we should use to first
educe the graph, as this algorithm is very fast (though it will have no
effect for random-looking graphs).
I have had it on my todo list for a while, and right now I am actually
writing the ong-awaited Gurobi interface for Sage `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11944#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
