|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Pluhár András: Gráfklaszterezés és speciális színezések kapcsolata |
|
|||
|
|
||||
|
||||
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 | ||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013
