Laboratory of Mathematical Logic at PDMI

Пятница, 9 апреля, комната 106. Начало в 18:00.

Докладчик: Ф. Фомин (Берген, Норвегия).

Тема: Exact (exponential) algorithm for treewidth.

Abstract

We present an algorithm which roughly needs 1.9601^n time to determine the treewidth of a graph on n vertices.