Kao najava akreditovanih doktorskih studija, koje će do kraja godine početi na Računarskom fakultetu, prof. dr Kristina Vušković i prof. dr Dragan Urošević održaće dva predavanja. U prvom, koje će biti na srpskom jeziku, predstaviće novi program doktorskih studija „Algoritmi, kombinatorika i optimizacija“. Dok će drugo predavanje biti stručno i na engleskom jeziku, u kome će profesoris predstaviti svoja dosadašnja istraživanja.
Predavanja će se obaviti 26.10.2009. u 17.30 č. u učionici 1.
Odeljak iz drugog predavanja prof. dr Kristine Vušković:
Title: The power of decomposition
Speaker: Kristina Vušković
Abstract: The power of decomposition is that it allows us to understand complex structures by breaking them down into simpler ones. Once these simpler structures are understood, this knowledge is propagated back to the original structure by understanding how their composition behaves. The use of decomposition in combinatorial theory had great success in solving some of the difficult problems such as obtaining polynomial time recognition algorithms for regular matroids, balanced matrices, perfect graphs, even-hole-free graphs, proving the famous Strong Perfect Graph Conjecture, as well as for obtaining combinatorial algorithms for some optimization problems for subclasses of graphs closed under taking induced subgraphs. In this talk we survey all these results, with the focus on the use and development of the decomposition techniques in the context of classes of graphs closed under taking induced subgraphs. The key distinguishing property of graph classes closed under taking induced subgraphs as opposed to for example being closed under minor taking (i.e. closed under deleting and contracting edges) is the need to use strong cutsets for their decomposition. This is what makes it very difficult to use such decomposition theorems for constructing algorithms and obtaining other interesting properties.