See by year See by month Jump to month

Pluhár András: Gráfklaszterezés és speciális színezések kapcsolata

Download as iCal file
Friday, 27. September 2019, 10:00 - 12:00

Absztrakt.

A kisvilág gráfok vizsgálatában az egyik alapvető kérdés, hogyan osztályozhatóak a pontjaik, mit jelentenek az osztályok, mennyire gyorsan kaphatók meg stb.
A klaszterezők jobbára azt célozzák, hogy a klasztereken belül sok, köztük kevés él húzódjon. Ún. szociális hálózatokban ez megfelelő és a kapott eredmények jók.
Technológiai hálózatok esetén más a helyzet és ez a terület kevésbé fejlődött. A pollinátor ill. bolt-beszállító páros gráf modell alapján újfajta klaszterezési szempontokat javaslunk, amelyek bizonyos feltételeket teljesítő színezések színosztályain alapulnak.
Ha adott egy H páros gráf, akkor G olyan jó színezéseit tekintjük, amelyekben bármely két színosztály között a H nem jelenik meg feszített részgráfként. A magyarázó erő maximalizálása céljából minimális színnel akarunk színezni, ezt \chi_H(G)-vel jelöljük.
Ahogy lenni szokott, a legtöbb esetben NP-teljes problémákhoz jutunk, bár néhány esetben van egyszerű megoldás.
Location : Bolyai Intézet, I. emelet, Riesz terem, Aradi vértanúk tere 1., Szeged

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013