Vi presenterar en metod för att lösa den oberoende uppsättning formulering av graf färg problemet (där det finns en variabel för varje oberoende uppsättning i grafen). Vi använder en kolonngenereringsmetod för implicit optimering av det linjära programmet vid varje nod av det gren-och-bundna trädet. Detta tillvägagångssätt löser snabbt små till måttliga storleksproblem, samtidigt som det kräver en lösning av ett delproblem i kulten och ett behov av sofistikerade regler för förgrening. Vi har också implementerat en exakt graffärgsalgoritm baserad på DSATUR för jämförelse. Genomförandedetaljer och beräkningserfarenhet presenteras.
Till exempel, Mehrotra och Trick REF presentera en formulering av graf färg problemet som undviker färg symmetrier.
A Column Generation Approach For Graph Coloring
{'venue': 'INFORMS Journal on Computing', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}