Advanced search
Start date

Graph coloring algorithms

Grant number: 20/09330-7
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Effective date (Start): November 01, 2020
Effective date (End): May 31, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Carla Negri Lintzmayer
Grantee:Wesley Lima de Araujo
Host Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil


A problem is of combinatorial optimization if it has as objective finding solutions on a domain that minimize or maximize a goal function. These characteristics are inherent to several important problems in the real world that come from different areas. Unfortunately, many combinatorial optimization problems are NP-hard, which leaves us with almost no hope to find efficient algorithms to solve them. The mathematical structure known as graph is used to model several combinatorial optimization problems, such as graph coloring problems, whose goal is is to find an specific rotulation for the vertices of the graph. Graph coloring problems are very important, because they can represent situations in which we have conflicts between objects and we want to separate them in groups according to some criteria, such as allocation problems. The objective of this project is to enlarge the research experience of the student in combinatorial optimization and design of algorithms by studying graph coloring problems and related algorithms.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: