Tardos Gábor:
Permutaciografok listaszinezese
<br><br>
Grafok lista szinezesi problemajanal minden csucshoz rendelunk egy szinlistat
es olyan valodi szinezest keresunk (azaz szomszedok legyenek kulonbozo
szinuek), ahol minden csucs szine a sajat listajarol van valasztva.
<br><br>

Termeszetesen ez a problema NP-teljes, meg akkor is, ha csak 3 szin van, es
azok minden csucs listajan szerepelnek. Permutacio-grafokra viszont adunk
hatekony lista-szinezesi algoritmust. Itt a hatekony azt jelenti, hogy
konstans sok szin eseten polinomialis. Permutacio graf pedig az olyan graf,
aminek csucsai sikbeli pontok es azok vannak ellel osszekotve, amelyek
egymastol ENY-DK iranyban vannak (az osszekoto egyenes meredeksege pozitiv).
<br><br>

Az eredmenyek ennel picit altalanosabbak, de ez a lenyeges specialis eset.
Abba a trendbe illeszkednek, hogy CSP problemak bonyolultsagat ne csak a
(kicsi, fix) target struktura alapjan osztalyozzuk, hanem a (nagy, input)
source struktura tipusa alapjan is. (Ez utobbi mondat megertese opcionalis,
az eloadas - ha egyaltalan - enelkul is elvezheto.)
<br><br>

A cikk Jessica Enrighttal es Lorna Stewarttal kozos.