果冻传媒

The Graph Algorithms group targets fundamental NP-hard optimization problems on graphs, with the goal of determining which parameters of a problem input control the difficulty of solving it optimally. The research done in the group therefore falls in the realm of parameterized algorithmics, an expanding subfield of algorithm design with a strong emphasis on graph problems. Graph parameters that represent a decomposition of the input graph into simpler pieces form a frequent topic of investigation. In addition to developing exact algorithms that are provably efficient on inputs in which a suitable complexity parameter is small, the group also works on preprocessing algorithms (kernelization) and other means to reduce the search space of algorithms solving NP-hard problems.

While the primary focus in the group is on theoretical research, practical applications are explored through master鈥檚 thesis projects. A successful series of projects deployed graph algorithms for the Steiner Tree problem to compute cost-efficient plans to install fiber-optic networks in urban areas.