#9618: Slight improvement to vertex_coloring
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.5.2
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: new => needs_review
Old description:
> We know that the chromatic number of a graph is more than its number of
> vertices divided by te size of its maximum independent set.
>
> Sage did not.
>
> Computations of max clique/independent set are way faster than coloring
> thanks to Cliquer, by the way !
>
> Nathann
New description:
We know that the chromatic number of a graph is more than its number of
vertices divided by te size of its maximum independent set.
Sage did not.
Computations of max clique/independent set are way faster than coloring
thanks to Cliquer, by the way !
The different is especially remarquable on random graphs :
After :
{{{
sage: g = graphs.RandomGNP(40,.3)
sage: g.graph6_string()
'geap`wp`?pwiec_g{m?smecc`cib?ocacgaa`qo?q?ggh?c...@_?qojwg@?????afdgro{fu_kgdqlacp`lohcpcafhbmjwrb]omrksaosx_`pi_ogrbb?u...@iaqpbqo'
sage: %timeit g.coloring(algorithm = "MILP")
5 loops, best of 3: 241 ms per loop
}}}
Before :
{{{
sage: g =
Graph('geap`wp`?pwiec_g{m?smecc`cib?ocacgaa`qo?q?ggh?c...@_?qojwg@?????afdgro{fu_kgdqlacp`lohcpcafhbmjwrb]omrksaosx_`pi_ogrbb?u...@iaqpbqo')
sage: %timeit g.coloring(algorithm = "MILP")
5 loops, best of 3: 361 ms per loop
}}}
And this difference should increase exponentially when the number of
vertices increases (on random graphs)
Nathann
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9618#comment:1>
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.
