Buchumschlag

Tree-Like Shortcuttings of Trees

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Le, Hung, Milenković, Lazar, Solomon, Shay, Than, Cuong
Format:	Preprint
Veröffentlicht:	2025
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

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

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

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
von: La, An, et al.
Veröffentlicht: (2025)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
von: Le, Hung, et al.
Veröffentlicht: (2023)

Towards Instance-Optimal Euclidean Spanners
von: Le, Hung, et al.
Veröffentlicht: (2024)

Light Spanners with Small Hop-Diameter
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
von: Le, Hung, et al.
Veröffentlicht: (2021)

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)

A Lossless Deamortization for Dynamic Greedy Set Cover
von: Solomon, Shay, et al.
Veröffentlicht: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
von: Bukov, Anton, et al.
Veröffentlicht: (2023)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

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

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

Reviving Thorup's Shortcut Conjecture
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
von: Le, Hung
Veröffentlicht: (2026)

Diameter Shortcut Sets on Temporal Graphs
von: Quantmeyer, Gerome
Veröffentlicht: (2025)

Shortcutting for Negative-Weight Shortest Path
von: Li, George Z., et al.
Veröffentlicht: (2025)

Shortcuts and Transitive-Closure Spanners Approximation
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

New weighted additive spanners
von: La, An, et al.
Veröffentlicht: (2024)

Closing the Gap Between Directed Hopsets and Shortcut Sets
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

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

Distances in Planar Graphs are Almost for Free!
von: Mozes, Shay, et al.
Veröffentlicht: (2026)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
von: Li, Xizhe, et al.
Veröffentlicht: (2026)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

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

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

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

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

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

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Moderate Dimension Reduction for $k$-Center Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2023)

Greedy Algorithms for Shortcut Sets and Hopsets
von: Bals, Ben, et al.
Veröffentlicht: (2025)

Perturbation-Resilient Trades for Dynamic Service Balancing
von: Sima, Jin, et al.
Veröffentlicht: (2024)

On Differentially Private Linear Algebra
von: Kaplan, Haim, et al.
Veröffentlicht: (2024)