|
|
||
|
IMADA -Department of Mathematics and Computer Science |
|
Harnessing structure to give efficient algorithms for hard problems on graphs is a common method to deal with their computational intractability. Traditionally, we want to give efficient algorithms assuming the input graph comes from a specific graph class, a set of graphs sharing a common structural property. Another way of measuring the complexity of a graph is via so-called width measures, which assign a number to each graph such that less complex graphs receive a lower width value. We can then design algorithms that are efficient on graphs of small width. In recent years, more and more well-studied graph classes have been shown to have bounded width, which implies that algorithms for bounded-width graphs often unify and extend several algorithms on graph classes at once. We discuss recent progress in this area and point out possibilities of extending this program to other domains than graphs. Moreover, we touch on the notion of diversity of solutions to combinatorial problems. Motivated by practical applications in which finding a single solution to a given problem is not enough, we want to find several solutions that are different from each other
SDU HOME | IMADA HOME Daniel Merkle |