Project Idea: Minimum Cut hos Københavns Universitet

Algorithms and Complexity

Forskerne prøver at forstå hvordan computere effektiv kan løse kombinatoriske problemer. For det meste arbejder forskerne teoretisk med hjælp fra matematikken. Desuden har de en stærk indflydelse på den virkelige verden, såsom at løse problemer inden for machine learning.

Forskning-sektionen er inddelt i tre områder:

  • Basic Algorithms

  • Big Data Analytics

  • Dynamic and Static Graph Algorithms and Data Structures

Læs mere her: https://di.ku.dk/english/research/ac/

 

ENGELSK VERSION:

The researchers try to understand how efficiently computers can solve combinatorial problems. Most of the work is theoretical using the power of mathematics, yet they have a strong track record of impact on the real world, e.g., focusing on problems recurring in machine learning.

The section is divided into three areas:

  • Basic Algorithms

  • Big Data Analytics

  • Dynamic and Static Graph Algorithms and Data Structures

Read more here: https://di.ku.dk/english/research/ac/

Background
The minimum cut problem (mincut) asks for a way to cut the smallest number of edges to
disconnect the graph. It is a basic tool for tasks on graphs. There are many recent advances
on this problem, e.g. sequential algorithms, parallel algorithms, and streaming algorithms.

Project description

  • Make a survey on the literature on mincut.

  • Implement some of the known mincut algorithms.

  • Experimentally test the performance of these on suitable graph instances.

  • Performance measure is mainly the running time but space requirement might be relevant too.

  •  Compare the results of these experiments with the theoretical bounds to see how they

    match up.

 

Supervision

Danupon Nanongkai, professer dnn@di.ku.dk

Husk at nævne, at du fandt dette opslag på KU Projekt & Job