Graphs, Algorithms and Optimization

This research area covers the study of different classes of graphs and some of the classical problems of graph theory when restricted to a given class such as maximum independent set, maximum clique, vertex and edge colouring, and minimum covering. Specific objectives for a problem may include determining its computational complexity for a particular graph class, proving that it is computationally intractable (NP-hard) for that class, or finding polynomial algorithms that solve it for any graph in that class.

 Another topic of investigation is the structural characterization of graph classes and the search for partial or total characterizations of them by means of forbidden structures. There are many open problems in otherwise well-studied graph classes for which this type of characterization has not yet been established.

 In optimization, we are actively engaged in the development of algorithms based on exact methods of solving integer linear programming problems and the implementation of heuristic methods for solving real-world problems.

 Many of the problems we are working on are motivated by real issues in operations research (OR), reflecting the strong involvement of our research with the Institute’s activities in OR-based technology transfer.