Beke Ákos (Pécsi Tudományegyetem): Klikkszám becslése lineáris programozással

Kombinatorikai optimalizálási problémák sok esetben átfogalmazhatók 0-1 lineáris programozási feladatra. Egy gráf klikkszámának meghatározására az egyik ismert módszer az élátfogalmazás, ahol a komplementer gráf élei határoznak meg lineáris egyenlőtlenség feltételeket, ez a csúcsok számában négyzetes feltételt tartalmaz.
   Előadásomban két olyan átfogalmazást ismertetek, amelyekben a feltételek száma megegyezik a csúcsok számával, továbbá ezen átfogalmazások két lehetséges megszorításáról lesz szó, amelyek valós relaxált esetén jobb felső korlátot eredményeznek a klikkszámra.
   Közös munka Szabó Sándorral és Zaválnij Bogdánnal.