A supernodal formulation of vertex colouring with applications in course timetabling

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00043680" target="_blank" >RIV/00216224:14330/10:00043680 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A supernodal formulation of vertex colouring with applications in course timetabling

Popis výsledku v původním jazyce

For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using "supernodes". In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90-112, 1978), a "supernode" is a complete subgraph, within which every pair of vertices have the same neighbourhood outside ofthe subgraph. A polynomial-time algorithm for obtaining the best possible partition of an arbitrary graph into supernodes is given. This makes it possible to use any formulation of vertex multicolouring to encode vertex colouring. Results of empirical tests on benchmark instances in graph colouring (DIMACS) and timetabling (Udine Course Timetabling) are also provided and discussed.

Název v anglickém jazyce

A supernodal formulation of vertex colouring with applications in course timetabling

Popis výsledku anglicky

For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using "supernodes". In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90-112, 1978), a "supernode" is a complete subgraph, within which every pair of vertices have the same neighbourhood outside ofthe subgraph. A polynomial-time algorithm for obtaining the best possible partition of an arbitrary graph into supernodes is given. This makes it possible to use any formulation of vertex multicolouring to encode vertex colouring. Results of empirical tests on benchmark instances in graph colouring (DIMACS) and timetabling (Udine Course Timetabling) are also provided and discussed.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F07%2F0205" target="_blank" >GA201/07/0205: Dynamické aspekty rozvrhování</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annals of Operations Research

ISSN

0254-5330

e-ISSN

—

Svazek periodika

179

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

26

Strana od-do

—

Kód UT WoS článku

000281246700007

EID výsledku v databázi Scopus

—