Mathematical Colloquim

 

PROGRAM


ODELJENJE ZA MATEMATIKU

MATEMATICKOG INSTITUTA SANU
                       OPSTI MATEMATICKI SEMINAR

NA MATEMATICKOM FAKULTETU U BEOGRADU



-- PROGRAM ZA JUN 2005 --

 

Petak, 03. jun 2005. u 14h, sala 2 MI SANU BG:


RAZGOVOR O PROJEKTIMA

Sastanak posvećen pripremama za novi ciklus projekata iz programa osnovnih istraživanja će voditi prof. Stevan Pilipović, predsednik Komisije za matematiku pri Ministarstvu za nauku i zaštitu životne sredine.

Petak, 10. jun 2005. u 14h, sala 2 MI SANU:

Prof. Miroslav Petrović, Bojana Borovićanin, Prirodno-matematički fakultet, Kragujevac
O POVEZANIM GRAFOVIMA SA MAKSIMALNIM INDEKSOM

Sadržaj. Biće prikazani neki od najnovijih rezultata koji se odnose na nalaženje grafova sa maksimalnim indeksom u odredjenim klasama grafova, izmedju ostalih i rezultati naših matematičara. Indeks grafa je najveća sopstvena vrednost (0,1) matrice susedstva grafa.
Posebno, bice posmatrana stabla, uniciklični, biciklični i triciklični grafovi sa n čvorova i odredjenim osobinama (sa fiksiranim brojem čvorova stepena 1, sa savršenim sparivanjima itd.). Značaj nalaženja grafova sa maksimalnim indeksom u ovim klasama potice iz činjenice da su upravo to grafovi sa najvećim stepenom iregularnosti (mera iregularnosti grafa je razlika \delta = \rho - \bar{d}, gde je \rho indeks, a \bar{d} srednja vrednost stepena čvorova grafa) u tim klasama.
Posmatraće se takodje i grafovi sa fiksiranim brojem čvorova i fiksiranim brojem artikulacionih čvorova, fiksiranim brojem mostova, sa osobinom da svake dve konture grafa imaju najviše jedan zajednički čvor-kaktusi itd.).

Petak, 17. jun 2005. u 14h, sala 2 MI SANU:

Prof. Kristina Vušković, School of Computing of University of Leeds (Leeds, UK)
THE USE OF THE DECOMPOSITION METHOD IN THE ANALYSIS OF PERFECT GRAPHS

Abstract: A graph G is perfect if for every node induced subgraph H of G, the chromatic number of H equals the size of its largest clique. This class of graphs was introduced by Berge in 1961, when he also conjectured that a graph is perfect if and only if it does not contain an odd hole nor an odd antihole. This famous conjecture was the focus of an enormous amount of exciting research, until it was finally proved by Chudnovsky, Robertson, Seymour and Thomas in 2002, and is now known as the Strong Perfect Graph Theorem. Soon afterwards another key open problem in the area was resolved by Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic, who obtained a polynomial time recognition algorithm for perfect graphs.
One important aspect of perfect graphs is that the following optimization problems: maximum weighted stable set, minimum weighted covering of vertices by cliques, maximum weighted clique and minimum weighted covering of vertices by stable sets, that are NP-complete in general, can be solved in polynomial time for perfect graphs. This result, due to Grotschel, Lovasz and Schrijver, uses the ellipsoid method. The question remains whether these four optimization problems can be solved for perfect graphs by polynomial time purely combinatorial algorithms, avoiding the numerical instability of the ellipsoid method.
This talk will survey the development of the decomposition techniques used in the analysis of perfect graphs that eventually led to the resolution of the Strong Perfect Graph Conjecture and a recognition algorithm for perfect graphs. We also present some of the most recent results in obtaining combinatorial algorithms for finding a clique of maximum weight in some subclasses of perfect graphs.




Rukovodioci Odeljenja za matematiku Matematickog instituta SANU i Opsteg matematickog seminara na Matematickom fakultetu u Beogradu, Stevan Pilipovic i Sinisa Vrecica predlazu zajednicki program rada naucnih sastanaka.

Predavanja ce se odrzavati na Matematickom Institutu (sala 2), petkom sa pocetkom u 14 casova. Odeljenje za matematiku je opsti seminar sa najduzom tradicijom u Institutu.

Svakog meseca, jedno predavanje ce biti odrzano na Matematickom Fakultetu u terminu koji ce biti posebno odredjen.

Molimo sve zainteresovane ucesnike u radu naucnih sastanaka da posebno obrate paznju na vreme odrzavanja svakog sastanka. Na Matematickom fakultetu su moguce izmene termina.

Obavestenje o programu naucnih sastanaka ce biti objavljeno na oglasnim tablama MI (Beograd), MF (Beograd), PMF (Novi Sad), PMF (Nis) i PMF (Kragujevac).

Odeljenje za matematiku Matematickog instituta SANU

Stevan Pilipovic

Opsti matematicki seminar na Matematickom fakultetu u Beogradu,

Sinisa Vrecica


Ako zelite da se obavestenja o Vasim naucnim skupovima pojave u Newsletter of EMS (European Mathematical Society) i na Internetu na lokaciji EMS, onda se obratite na emsvesti@mi.sanu.ac.yu gde cete dobiti format obavestenja.