direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Independent Set in P_t-free graphs

Tomohiro Koana (TU Berlin)

 

The independent set problem is known to be NP-hard in general. There has been an enormous interest in the problem restricted to Pt-free graphs, where Pt is an induced path of order t. It has long been known that the problem can be solved in polynomial time for P4-free graphs. Recently, there was a breakthrough by Lokshtanov et al. (SODA 2014), who showed that  the problem can be solved in polynomial time on P5-free graphs as well. Followed by this positive result, Grzesik et al. (arXiv 2017) extended the result to P6-free graphs. In this talk, two subexponential time algorithms for the independent set problem in Pt-free (for any fixed t) graphs are going to be presented.

 

Date
Speaker
Location
Language
10.01.2019
16:15
Tomohiro Koana
TEL 512
English

Back to the research colloquium site.

To top

Zusatzinformationen / Extras