Randomized contractions meet lean decompositions

We show an algorithm that, given an $n$-vertex graph $G$ and a parameter $k$, in time $2^{O(k \log k)} n^{O(1)}$ finds a tree decomposition of $G$ with the following properties: * every adhesion of the tree decomposition is of size at most $k$, and * every bag of the tree decomposition is $(i,i)...

Szczegółowa specyfikacja

Opis bibliograficzny

Główni autorzy:	Cygan, Marek, Komosa, Paweł, Lokshtanov, Daniel, Pilipczuk, Michał, Pilipczuk, Marcin, Saurabh, Saket, Wahlström, Magnus
Format:	Artykuł
Wydane:	2018
Hasła przedmiotowe:	Data Structures and Algorithms
Dostęp online:	https://arxiv.org/abs/1810.06864 http://arxiv.org/abs/1810.06864
Etykiety:	Dodaj etykietę Nie ma etykietki, Dołącz pierwszą etykiete!