Description
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 Bolyai Intézet (Szeged, Aradi vértanúk tere 1) Riesz termében lesz.