In this paper, we present an approximate distance oracle for fault-tolerant Euclidean spanners. An $f$-fault-tolerant Euclidean $t$-spanner for a point set $V \subset \mathbb{R}^d$ is a graph $G=(V,E)$ where, for any two points $p$ and $q$ in $V$ and a set $F$ of $f$ vertices of $V$, the distance between $p$ and $q$ in $G-F$ is at most $t$ times their Euclidean distance. Given an $f$-fault-tolerant 
Euclidean $t$-spanner $G$ and a constant $\varepsilon$ for constants $t$ and $f$,
we can construct a data structure of size $O(m\log n)$ in $O(m\log^2 n)$ time so that an $(1+\varepsilon)$-approximate distance in $G-F$ between $s$ and $s'$ can be computed in constant time for any two vertices $s$ and $s'$ and a set $F$ of $f$ failed vertices. Additionally, we can construct a data structure of size $O(m\log n\log\log n)$ in $O(m^2\log^2 n)$ so that an $(1+\varepsilon)$-approximate shortest path in $G-F$ between $s$ and $s'$ can be compute in $O(\log^2 n\log\log n)$ time for any two vertices $s$ and $s'$ and a set $F$ of failed vertices.

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

Main Track - PRS

technical paper

We are pleased to announce the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), which will be held in Vancouver, British Columbia at the Vancouver Convention Centre – West Building from 20-27 February, 2024.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-24 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

We expect for AAAI-24 to be an in-person conference – one author of all accepted papers will be expected to present work in person unless there are exceptional circumstances that prevent this.<br><br><br><br>

In order to access the AAAI-24 event page you need to register [here](https://aaai.org/aaai-conference/registration/)

AAAI 2024

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. 

kyungjin cho

1

3

SHORT BIO

Presentations

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES