The main goal of the lecture is to give the students a first introduction the graph partitioning and clustering problems. This includes a set of ``easier'' subproblem problems and models that will be explained at the point of occurrence.
Graphs are frequently used by computer scientists as abstractions when modeling an application problem. Cutting a graph into smaller pieces is one of the fundamental algorithmic operations. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), partitioning or clustering large graphs is often an important subproblem for complexity reduction or parallelization. With the advent of even larger instances in applications such as scientific simulation, social networks, or road networks, graph partitioning and graph clustering therefore becomes highly important, multifaceted, and challenging.
The lecture will cover many different aspects of graph partitioning and graph clustering. After defining these problems and its objective functions properly, we show the hardness of some variants and present algorithms having a global view such as integer linear programs or spectral techniques. A large amount of the lecture is centered around the multilevel scheme which is explained in high detail for the graph partitioning problem. We then cover parallel, (semi-)external and evolutionary algorithms to tackle the problems. In addition, we talk about the currently most important algorithms to cluster graphs effectively.
Please register in TISS for this course.
