Opened 9 years ago

Closed 9 years ago

#9618 closed enhancement (fixed)

Slight improvement to vertex_coloring

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

Description (last modified by ncohen)

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?CRWQ@_?QOJwG@?????AFDGRO{FU_KGDQLACp`LOHcPCAFHBMJwRB]OMRKSAOSx_`PI_OgRBB?UBTG@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?CRWQ@_?QOJwG@?????AFDGRO{FU_KGDQLACp`LOHcPCAFHBMJwRB]OMRKSAOSx_`PI_OgRBB?UBTG@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

Attachments (1)

trac_9618.patch (1.3 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (4)

Changed 9 years ago by ncohen

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by rlm

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

comment:3 Changed 9 years ago by jdemeyer

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