direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Parametrised Algorithms for Finding Triangles in Graphs - Detection, Counting and Enumeration

Matthias Bentert (TU Berlin)

 

Finding triangles in graphs is a simple yet frequently required task that is well known to be solvable in polynomial time. However, no algorithm is known that solves the task in worst case time at most quadratic in the number of vertices of the input graph. We study the problem from a parametrised point of view, recently referred to as "FPT in P". Herein, we consider the problem given along with a parameter, e.g. the degeneracy of the input graph. We give a broad overview on our results with respect to different parametrisations. On the one hand, we present parametrised algorithms as well as kernelisations. On the other hand, we introduce a new notion of hardness that is used to prove that if certain parameters are bounded, then finding triangles in graphs cannot be done any faster than on graphs with unbounded parameters.

 

Date
Speaker
Location
Language
08.12.2016
16:15
Matthias Bentert
TEL 512
English

Back to the research colloquium site.

Zusatzinformationen / Extras