דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
דוד וייץ (גוגל - טכניון)
event date icon
יום שלישי, 22.11.2022, 14:30
event location icon
טאוב 337
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. This answers in the affirmative the value version of a major open question, repeatedly asked in the dynamic graph algorithms literature. Based on an upcoming SODA 2023 best paper, joint with Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak.