195.084 Graph Partitioning and Graph Clustering in Theory and Practice
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

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.

Weitere Informationen

The lecturer of this course will be Dr. Christian Schulz / KIT Karlsruhe Institute of Technology.

Lecture notes will be available.

 

 

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di10:00 - 12:0006.10.2015 - 15.12.2015EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi14:00 - 16:0013.01.2016 - 20.01.2016EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi14: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
Di06.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di13.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di20.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di27.10.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di03.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di10.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di17.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di24.11.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di01.12.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Di15.12.201510:00 - 12:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi13.01.201614:00 - 16:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi20.01.201614:00 - 16:00EI 6 Eckert HS Graph Partitioning and Graph Clustering in Theory and Practice
Mi27.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.

Weitere Informationen

Sprache

Englisch