Přístupnostní navigace
E-application
Search Search Close
Publication detail
ŠEDA, M.
Original Title
Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS
Type
journal article in Scopus
Language
English
Original Abstract
The graph colouring problem is one of the most studied combinatorial optimisation problems, one with many applications, e. g., in timetabling, resource assignment, team-building problems, network analysis, and cartography. Because of its NP-hardness, the question arises of its solvability for larger instances. Instead of the traditional approaches based on the use of approximate or stochastic heuristic methods, we focus here on the direct use of an integer programming model in the GAMS environment. This environment makes it possible to solve instances much larger than in the past. Neither does it require complex parameter settings or statistical evaluation of the results as in the case of stochastic heuristics because the computational core of software tools, nested in GAMS, is deterministic in nature.
Keywords
graph colouring, independent set, NP-hard problem, integer programming, GAMS
Authors
Released
31. 5. 2023
Publisher
WSEAS
ISBN
1790-2769
Periodical
WSEAS Transactions on Systems
Year of study
22
Number
May
State
Hellenic Republic
Pages from
532
Pages to
537
Pages count
6
URL
https://wseas.com/journals/systems/2023/b085102-033(2023).pdf
Full text in the Digital Library
http://hdl.handle.net/11012/213661
BibTex
@article{BUT183950, author="Miloš {Šeda}", title="Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS", journal="WSEAS Transactions on Systems", year="2023", volume="22", number="May", pages="532--537", doi="10.37394/23202.2023.22.53", issn="1790-2769", url="https://wseas.com/journals/systems/2023/b085102-033(2023).pdf" }