#11944 closed defect (fixed)
Update Graph.clique_maximum to use MILP
| Reported by: | ncohen | Owned by: | tbd |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.8 |
| Component: | graph theory | Keywords: | |
| Cc: | dcoudert | Merged in: | sage-4.8.alpha0 |
| Authors: | Nathann Cohen | Reviewers: | David Coudert |
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | #11846, #11928 | Stopgaps: |
Status badges
Description (last modified by )
Attachments (1)
Change History (10)
comment:1 Changed 10 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Description modified (diff)
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to defect
Changed 10 years ago by
comment:2 Changed 10 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to needs_info
comment:3 Changed 10 years ago by
- Status changed from needs_info to needs_review
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
comment:4 Changed 10 years ago by
- Status changed from needs_review to positive_review
Thank you Nathann for the prompt answer.
So my review for this patch is positive.
comment:5 Changed 10 years ago by
Thaaaaaaaaaaaanks !! :-)
Nathann
comment:6 Changed 10 years ago by
- Dependencies changed from 11846, 11928 to #11846, #11928
comment:7 Changed 10 years ago by
- Merged in set to sage-4.7.3.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:9 Changed 10 years ago by
- Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
- Milestone set to sage-4.8
The patch is working correctly, and the documentation is displayed properly.
I have a question concerning the algorithms: wouldn't it be faster to first decompose the graph into 2-connected components, and then try the algorithm on each of them ? This could be interesting for sparse graphs.