Nagy-György Judit: Páros gráfok online színezésének tanácsadói bonyolultságáról

Az online algoritmus az inputot részletekben, jelen esetben csúcsonként kapja, amely színéről azonnali visszavonhatatlan döntést kell hoznia a jövő ismerete nélkül.  A versenyképességi elemzés az online és optimális célfüggvényérték hányadosát vizsgálja legrosszabb esetben. A tanácsadói bonyolultság azt mondja meg, ha van egy mindentudó orákulumunk, akkor hány bitnyi információt kell megkérdeznie tőle az online algoritmusnak, hogy elérjen egy adott versenyképességi hányadost. A páros gráfokra és fákra vonatkozó ismert eredményeket és nyitott kérdéseket nézzük meg.