|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
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. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013