Theory Seminar, Wednesday Dec 11: Itai Boneh (Reichman and Haifa) - Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
1 view
Skip to first unread message
Arnold Filtser
Dec 10, 2024, 6:04:30 AM12/10/24
to BIU Theory Seminar, barbun...@gmail.com
The talk by Itai happens tomorrow! (Wed Dec 11, at 12)
Speaker: Itai Boneh (Reichman and Haifa)
Title: Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs.
Abstract: We present a labeling scheme that assigns labels of size Õ(1) to the vertices of a directed weighted planar graph G, such that for any fixed ϵ>0 from the labels of any three vertices s, t and f one can determine in Õ(1) time a (1+ϵ)-approximation of the s-to-t distance in the graph G \ {f}.
For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting.
Even for the easier case of reachability, Õ(1) queries were known only with a centralized oracle of size Õ(n) [SODA 21].
Joint work with Shiri Chechik, Shay Golan, Shay Mozes, and Oren Weimann.
Speaker: Itai Boneh (Reichman and Haifa)
Title: Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs.
Abstract: We present a labeling scheme that assigns labels of size Õ(1) to the vertices of a directed weighted planar graph G, such that for any fixed ϵ>0 from the labels of any three vertices s, t and f one can determine in Õ(1) time a (1+ϵ)-approximation of the s-to-t distance in the graph G \ {f}.
For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting.
Even for the easier case of reachability, Õ(1) queries were known only with a centralized oracle of size Õ(n) [SODA 21].
Joint work with Shiri Chechik, Shay Golan, Shay Mozes, and Oren Weimann.
Reply all
Reply to author
Forward
0 new messages