Attributes | Values |
---|
rdf:type
| |
Description
| - 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 %22supernodes%22. In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90-112, 1978), a %22supernode%22 is a complete subgraph, within which every pair of vertices have the same neighbourhood outside of the 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.
- 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 %22supernodes%22. In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90-112, 1978), a %22supernode%22 is a complete subgraph, within which every pair of vertices have the same neighbourhood outside of the 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. (en)
|
Title
| - A supernodal formulation of vertex colouring with applications in course timetabling
- A supernodal formulation of vertex colouring with applications in course timetabling (en)
|
skos:prefLabel
| - A supernodal formulation of vertex colouring with applications in course timetabling
- A supernodal formulation of vertex colouring with applications in course timetabling (en)
|
skos:notation
| - RIV/00216224:14330/10:00043680!RIV11-GA0-14330___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(GA201/07/0205), Z(MSM0021622419)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216224:14330/10:00043680
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Annals of Operations Research
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Rudová, Hana
- Burke, Edmund
- Mareček, Jakub
- Parkes, Andrew
|
http://linked.open...ain/vavai/riv/wos
| |
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |
http://localhost/t...ganizacniJednotka
| |