Leírás
EGERVÁRY SZEMINÁRIUM
Absztrakt:
Kosztolányi Katával közös munka.
A népszerű párosítások a stabilok gyengítéseinek tekinthetők, ahol a
lokális blokkolási struktúra helyet csak globális blokkoló
struktúrákat tiltunk meg: a csúcsok adott preferenciasorrendjei
mellett egy párosítás népszerű, ha nincs olyan párosítás, mely nyerne
vele szemben egy képzeletbeli választáson.
Korábban ismert volt, hogy adott párosítás népszerűségének eldöntése
súlyozott párosítás problémával kezelhető, és páros esetben lineáris
időben megoldható.
Megmutatjuk, hogy a lineáris idő általános gráfoknál is elérhető. A
módszer lényege, hogy a súlyozott párosítás probléma helyett egy
maximális párosítás tesztelési feladatra vezetjük vissza a kérdést. A
megfigyelésből a poliéderes leírásbeli tanú struktúrája is
egyszerűsödik a korábbiakhoz képest.