|
|
|
|
|
|
|
|
See by year | See by month | Jump to month | |
|
Pluhár András: Gráfklaszterezés és speciális színezések kapcsolata |
|
|
|
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