Professor Vadim Lozin will give a lecture at the laboratory seminar
Event ended
Professor of the University of Warwick (UK) Vadim Lozin will give a lecture "Cliques, Coloring and Satisfiability: from structure to algorithms" at the laboratory seminar on June, 4 at 2 p.m.
Abstract:
Cliques, coloring and satisfiability are three central problems of theoretical computer science each of which is generally NP-hard. On the other hand, each of them may become tractable when restricted to instances of particular structure. In this talk we analyze how the structure of the input can affect the computational complexity of these problems. We also discuss some algorithmic tools to solve the problems with a focus given to transformations of graphs and of CNF formulas.
Place: 136, Rodionova St., room №401.
All are invited!
Date
4 June
15:00