Év szerint Hónap szerint Ugrás a hónaphoz

Nagy-György Judit: Fák online színezésének tanácsadói bonyolultsága

iCal fájl letöltése
Péntek, 21. Október 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.

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013