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

Download as iCal file
Friday, 21. October 2022, 10:00 - 11:30
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.

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013