Combinatorial Optimization Algorithms for Hereditary Graph Classes

点击翻译按钮获取中文摘要

Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society. The applications include diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. Problems such as assigning frequencies to mobile telephones, can be modeled using graphs, and then the problem is reduced to coloring the vertices of the graph so that no two adjacent vertices receive the same color (of course the interest is in the minimum number of colors, and this is called the chromatic number of a graph). Many other applications in the real world reduce to the same coloring problem on graphs. Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). One of the ways to deal with this situation is to find classes of graphs for which these problems can be solved in polynomial time.This project will focus on developing techniques for obtaining combinatorial optimization algorithms by expoliting structural analysis of hereditary graph classes. Many important graph classes are hereditary (i.e. closed under taking induced subgraphs), such as perfect graphs. For a difficult optimization problem, such as finding the chromatic number of a graph or the size of its largest clique, to be solvable in polynomial time for a given class, it means that this class must have some strong structure. The proposed research is about trying to understand what is this strong structure that will allow polynomial time combinatorial optimization algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.