Seminar za računarstvo i primenjenu matematiku, 6. april 2021.

Naredni sastanak Seminara biće održan onlajn u utorak, 6. aprila 2021. sa početkom u 14:15.

Predavač: Jozef Kratica, Matematički institut SANU

Naslov predavanja: NEKE OSOBINE PROBLEMA {k}-PAKOVANjA GRAFOVA

Apstrakt: Za dati graf G i pozitivan ceo broj k, funkciju f:V(G)→N [0} nazivamo funkcijom {k}-pakovanja ako za svaki čvor v\in V(G) vrednost f(N[v]) ne prelazi k. Maksimalnu moguću vrednost f(V(G)) u odnosu na sve funkcije {k}-pakovanja obeležavamo sa L{k}(G) a dati problem nazivamo problem {k}-pakovanja. U ovom izlaganju će biti prikazani novi rezultati u vezi ovog problema. Prvo će biti prikazana veza između slučajeva k=1, k>=2 i relaksacije odgovarajućeg problema celobrojnog linearnog programiranja, kao i dovoljni uslovi optimalnosti. U drugom koraku će biti data konstruktivna procedura za nalaženje odgovarajućih vrednosti k, za koje je L{k}(G) moguće rešiti u polinomijalnom vremenu izvršavanja. Zatim će biti uspostavljena veza između funkcije {1}-pakovanja i poznatog problema nalaženja maksimalnog skupa izolovanih čvorova (independent set number). Na kraju će biti date egzaktne vrednosti L{k}(G) za neke specijalne klase grafova, kao i nekoliko opštih gornjih i donjih granica.

Napomena:
Zbog trenutne epidemiološke situacije, redavanja se mogu pratiti isključivo na daljinu preko linka
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So


 Ostavite vaš komentar 

Komentari(0)

Nažalost nije moguće ostaviti komentar.