Copertina

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Horowicz, Noam, Kopelowitz, Tsvi
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
di: Kopelowitz, Tsvi, et al.
Pubblicazione: (2023)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
di: Huang, Shang-En, et al.
Pubblicazione: (2016)

Approximate Distance Sensitivity Oracles in Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2023)

New Diameter Approximations via Distance Oracle Techniques
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
di: Dey, Dipan, et al.
Pubblicazione: (2025)

Hamming Distance Oracle
di: Boneh, Itai, et al.
Pubblicazione: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
di: Yan, Shuyi
Pubblicazione: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
di: Harada, Kaito, et al.
Pubblicazione: (2024)

Distributed Distance Sensitivity Oracles
di: Manoharan, Vignesh, et al.
Pubblicazione: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Improved Algorithms for Clustering with Noisy Distance Oracles
di: Pradhan, Pinki, et al.
Pubblicazione: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Path-Reporting Distance Oracles with Linear Size
di: Neiman, Ofer, et al.
Pubblicazione: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
di: Dey, Dipan, et al.
Pubblicazione: (2024)

Dynamic $(Δ+ 1)$ Vertex Coloring
di: Benson-Tilsen, Noam
Pubblicazione: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
di: Dey, Dipan, et al.
Pubblicazione: (2024)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
di: Neiman, Ofer, et al.
Pubblicazione: (2026)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
di: Kadria, Avi, et al.
Pubblicazione: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
di: Manoharan, Vignesh, et al.
Pubblicazione: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
di: Boneh, Itai, et al.
Pubblicazione: (2025)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
di: Elkin, Michael, et al.
Pubblicazione: (2023)

Hardness and Approximation for Coloring Digraphs
di: Chalermsook, Parinya, et al.
Pubblicazione: (2026)

Advances in Exact and Approximate Group Closeness Centrality Maximization
di: Schulz, Christian, et al.
Pubblicazione: (2026)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
di: Mo, Guanlin, et al.
Pubblicazione: (2024)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
di: Terao, Tatsuya
Pubblicazione: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
di: Chitnis, Rajesh, et al.
Pubblicazione: (2024)

Approximate Circular Pattern Matching under Edit Distance
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2024)

Hyper-distance Oracles in Hypergraphs
di: Preti, Giulia, et al.
Pubblicazione: (2023)

Approximately Counting Knapsack Solutions in Subquadratic Time
di: Feng, Weiming, et al.
Pubblicazione: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
di: Mao, Xiao, et al.
Pubblicazione: (2026)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
di: Teshigawara, Kanata, et al.
Pubblicazione: (2026)

Combinatorial Optimization using Comparison Oracles
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

Fault-Tolerant ST-Diameter Oracles
di: Bilò, Davide, et al.
Pubblicazione: (2023)

Optimal Sensitivity Oracle for Steiner Mincut
di: Bhanja, Koustav
Pubblicazione: (2024)

Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching
di: Stamoulis, Georgios
Pubblicazione: (2026)

Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
di: Siqueira, Gabriel, et al.
Pubblicazione: (2025)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
di: Kolmogorov, Vladimir, et al.
Pubblicazione: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
di: Kosinas, Evangelos
Pubblicazione: (2025)

Graph Reconstruction with a Connected Components Oracle
di: Harviainen, Juha, et al.
Pubblicazione: (2025)