|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Nagy-György Judit: Fák online színezésének tanácsadói bonyolultsága |
|
|||
|
|
||||
|
||||
| Online algoritmusok tanácsadói bonyolultsága többféleképpen definiálható. A leggyakrabban alkalmazott szalag modellben egy orákulum ír egy tanácsszalagra és adott versenyképesség eléréséhez az algoritmus által olvasott bitek száma a tanácsadói bonyolultság. Online színezés esetén csak az útra és még néhány speciális gráfosztályra van éles (vagy nagyságrendileg megadott) eredmény, már fákra is csak annyi volt eddig ismert, hogy o(n) tanácsbit nem elég konstans versenyképesség eléréséhez. Böckenhauer és mtsai adtak felső korlátot páros gráfok esetén a tanácsadói bonyolultságra, ezt továbbgondolva a fák online színezésének tanácsadói bonyolultsága nagyságrendileg megadható. Az előadás a Riesz teremben lesz. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013
