Graph Algorithms

Graph theory plays an essential role within algorithmics, partly because graphs often occur as the underlying model for the problems treated and partly because the area of graph theory offers a large number of challenging algorithmic problems. Graphs are an essential tool for modelling many practical problems, hence making algorithmic graph theory an important area with many practical applications.

Graph algorithms are treated both in sequential and parallel versions. The group is interested in many different areas including graph connectivity and  problems concerning augmentation of  the connectivity through operations such as adding new edges, as well as the study of graph classes where NP-complete problems such as hamiltonian cycle, clique etc. can be solved in polynomial time. In particular a large number of results have been obtained for digraphs which are generalizations of tournaments. Other problems researched by the group include recognition of graph classes and many variants of graph colouring problems. We are also very interested in structural results as these are very often the key step in developing efficient algorithms.

Besides exact algorithms the group is also very interested in heuristics and approximative algorithms for graph problems. In this area we have worked on problems such as timetabling, graph colouring, vehicle routing, making a graph 2-edge connected by adding a minimum number of new edges, problems concerning edge-disjoint trees with weights on the edges and the so-called central tree problem.

The group is also very interested in applications of graph algorithms and methodology to practical problems. In particular we are working on industrial scheduling problems on variants of the TSP problem within the Danish home care sector and on applications of graph  algorithms to problems in biology.

The group collaborates with many other institutions including University of Victoria, Simon Fraser University, Universite de Montpellier, Universite de Bordeaux 1, Royal Holloway University of London, Eotvos University Budapest, University of Leipzig, University of Bergen.

Jørgen Bang-Jensen
Marco Chiarandini
Lene Monrad Favrholdt

To give you the best possible experience, this site uses cookies Read more about cookies

Accept cookies