TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 12.01.2017

isti-logo

Page Content

to Navigation

Assessing the Computational Complexity of Multi-Layer Subgraph Detection

Hendrik Molter (TU Berlin)

 

Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple types of relationships (edges in different layers). We chart the border of computational (in)tractability for the class of subgraph detection problems of multi-layer graphs, including fundamental problems such as maximum matching, finding certain clique relaxations (motivated by community detection), or path problems. Mostly encountering hardness results, sometimes even for two or three layers, we can also spot some islands of tractability.

 

Date
Speaker
Location
Language
12.01.2017
16:15
Hendrik Molter
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe