# 195.084 Graph Partitioning and Graph Clustering in Theory and Practice Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_1y",{id:"j_id_1y",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});});

2015W, VU, 2.0h, 3.0EC

## Merkmale

• Semesterwochenstunden: 2.0
• ECTS: 3.0
• Typ: VU Vorlesung mit Übung

## Ziele der Lehrveranstaltung

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.

## Inhalt der Lehrveranstaltung

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.

## LVA Termine

TagZeitDatumOrtBeschreibung
Di.10:00 - 12:0006.10.2015 - 15.12.2015EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi.14:00 - 16:0013.01.2016 - 20.01.2016EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi.14:00 - 16:0027.01.2016EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Graph Partitioning and Graph Clustering in Theory and Practice - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.06.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.13.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.20.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.27.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.03.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.10.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.17.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.24.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.01.12.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di.15.12.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi.13.01.201614:00 - 16:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi.20.01.201614:00 - 16:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi.27.01.201614:00 - 16:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice

## LVA-Anmeldung

Von Bis Abmeldung bis
08.09.2015 08:00 05.10.2015 23:59 05.10.2015 23:59

Anmeldemodalitäten:

Please register in TISS for this course.

## Curricula

StudienkennzahlSemesterAnm.Bed.Info
786 881 Informatik
PhD Vienna PhD School of Informatics

## Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Englisch