Buchumschlag

Distances in Planar Graphs are Almost for Free!

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Mozes, Shay, Prigan, Daniel
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Approximate Light Spanners in Planar Graphs
von: Le, Hung, et al.
Veröffentlicht: (2025)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
von: Gahlawat, Harmender, et al.
Veröffentlicht: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Almost Linear Size Edit Distance Sketch
von: Koucký, Michal, et al.
Veröffentlicht: (2024)

Hamming Distance Oracle
von: Boneh, Itai, et al.
Veröffentlicht: (2024)

Distance Approximating Minors for Planar and Minor-Free Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

Connectivity Labeling in Faulty Colored Graphs
von: Petruschka, Asaf, et al.
Veröffentlicht: (2024)

Bellman-Ford in Almost-Linear Time for Dense Graphs
von: Li, George Z., et al.
Veröffentlicht: (2026)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
von: Goyal, Dishant, et al.
Veröffentlicht: (2024)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
von: Hammer, Nina, et al.
Veröffentlicht: (2022)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2026)

Optimal Distance Labeling for Permutation Graphs
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2024)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
von: Di Battista, Giuseppe, et al.
Veröffentlicht: (2024)

Paths and Intersections: Exact Emulators for Planar Graphs
von: Li, George Z., et al.
Veröffentlicht: (2025)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
von: Brand, Jan van den, et al.
Veröffentlicht: (2024)

Optimizing Distances for Multi-Broadcast in Temporal Graphs
von: Carnevale, Daniele, et al.
Veröffentlicht: (2026)

Graph Exploration: The Impact of a Distance Constraint
von: Devismes, Stéphane, et al.
Veröffentlicht: (2024)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
von: Bentert, Matthias, et al.
Veröffentlicht: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
von: Neiman, Ofer, et al.
Veröffentlicht: (2026)

Distance Adjustment of a Graph Drawing Stress Model
von: Onoue, Yosuke
Veröffentlicht: (2024)

On the Adversarial Robustness of Online Importance Sampling
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Expander Decomposition with Almost Optimal Overhead
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Deterministic Mincut in Almost-Linear Time
von: Li, Jason
Veröffentlicht: (2021)

Almost succinct representation of maximal palindromes
von: Mieno, Takuya, et al.
Veröffentlicht: (2025)

Network Unreliability in Almost-Linear Time
von: Cen, Ruoxu, et al.
Veröffentlicht: (2025)

Almost-Optimal Sublinear Additive Spanners
von: Tan, Zihan, et al.
Veröffentlicht: (2023)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2025)

Clustered Planarity Variants for Level Graphs
von: Fink, Simon D., et al.
Veröffentlicht: (2024)

Structural Parameterizations of $k$-Planarity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)