About: A supernodal formulation of vertex colouring with applications in course timetabling

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A supernodal formulation of vertex colouring with applications in course timetabling Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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	P Z
http://linked.open...avai/riv/aktivity	P(GA201/07/0205), Z(MSM0021622419)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Rudová, Hana Mareček, Jakub Burke, Edmund
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	245011
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/10:00043680
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming (en)
http://linked.open.../riv/klicoveSlovo	Module Integer programming Graph colouring Multicolouring Supernode Vertex colouring
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[ACFD34C72216]
http://linked.open...i/riv/nazevZdroje	Annals of Operations Research
http://linked.open...in/vavai/riv/obor	BB
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Dynamic aspects of scheduling
http://linked.open...UplatneniVysledku	2010
http://linked.open...v/svazekPeriodika	179
http://linked.open...iv/tvurceVysledku	Rudová, Hana Burke, Edmund Mareček, Jakub Parkes, Andrew
http://linked.open...ain/vavai/riv/wos	000281246700007
http://linked.open...n/vavai/riv/zamer	Highly Parallel and Distributed Computing Systems
issn	0254-5330
number of pages	26 (xsd:int)
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software