direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras