Семинар за рачунарство и примењену математику, 6. април 2021.
- 02. Април, 2021
- Коментари (0)
Наредни састанак Семинара биће одржан онлајн у уторак, 6. априла 2021. са почетком у 14:15.
Предавач: Јозеф Кратица, Математички институт САНУ
Наслов предавања: НЕКЕ ОСОБИНЕ ПРОБЛЕМА {k}-ПАКОВАЊА ГРАФОВА
Апстракт: За дати граф G и позитиван цео број k, функцију f:V(G)→N [0} називамо функцијом {k}-паковања ако за сваки чвор v\in V(G) вредност f(N[v]) не прелази k. Максималну могућу вредност f(V(G)) у односу на све функције {k}-паковања обележавамо са L{k}(G) а дати проблем називамо проблем {k}-паковања. У овом излагању ће бити приказани нови резултати у вези овог проблема. Прво ће бити приказана веза између случајева k=1, к>=2 и релаксације одговарајућег проблема целобројног линеарног програмирања, као и довољни услови оптималности. У другом кораку ће бити дата конструктивна процедура за налажење одговарајућих вредности k, за које је L{k}(G) могуће решити у полиномијалном времену извршавања. Затим ће бити успостављена веза између функције {1}-паковања и познатог проблема налажења максималног скупа изолованих чворова (independent set number). На крају ће бити дате егзактне вредности L{k}(G) за неке специјалне класе графова, као и неколико општих горњих и доњих граница.
Напомена:
Због тренутне епидемиолошке ситуације, редавања се могу пратити искључиво на даљину преко линка
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So
Коментари(0)