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.
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.