Предавања проф. Кристине Вушковић на РАФ-у

Као најава акредитованих докторских студија, које ће до краја године почети на Рачунарском факултету, проф. др Кристина Вушковић и проф. др Драган Урошевић одржаће два предавања. У првом, које ће бити на српском језику, представиће нови програм докторских студија „Алгоритми, комбинаторика и оптимизација“. Док ће друго предавање бити стручно и на енглеском језику, у коме ће професори представити своја досадашња истраживања.

Предавања ће се одржати 26.10.2009. у 17.30 ч. у учионици број 1.

Обавезно је пријављивање за предавање на е-маил: marketing @ raf.edu.rs.

Одељак из другог предавања проф. др Кристине Вушковић:

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.

1298-predavanja-prof-kristine-vuskovic-na-raf-u