Buchumschlag

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodwin, Greg, Wang, Lily
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Notes on the Linear Algebraic View of Regularity Lemmas
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Light Edge Fault Tolerant Graph Spanners
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
von: Bodwin, Greg, et al.
Veröffentlicht: (2026)

A Unified View of Graph Regularity via Matrix Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2019)

An Alternate Proof of Near-Optimal Light Spanners
von: Bodwin, Greg
Veröffentlicht: (2023)

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Improved Online Reachability Preservers
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Parameterized Shortest Path Reconfiguration
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

Multiplicative Spanners in Minor-Free Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
von: Koehler, Frederic, et al.
Veröffentlicht: (2025)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
von: Bodwin, Greg, et al.
Veröffentlicht: (2023)

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

On the Two Paths Theorem and the Two Disjoint Paths Problem
von: Humeau, Samuel, et al.
Veröffentlicht: (2025)

Are there graphs whose shortest path structure requires large edge weights?
von: Bernstein, Aaron, et al.
Veröffentlicht: (2023)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2025)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
von: Geis, Lukas, et al.
Veröffentlicht: (2024)

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

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

Minor Containment and Disjoint Paths in almost-linear time
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

Approximate Counting in Local Lemma Regimes
von: Mann, Ryan L., et al.
Veröffentlicht: (2025)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
von: Kuhlmann, Stefan, et al.
Veröffentlicht: (2025)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
von: Dhawan, Abhishek
Veröffentlicht: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Improved 2-Approximate Shortest Paths for close vertex pairs
von: Gupta, Manoj
Veröffentlicht: (2025)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

Improved exploration of temporal graphs
von: Bastide, Paul, et al.
Veröffentlicht: (2025)

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

On Constrained and k Shortest Paths
von: Bendahi, Abderrahim, et al.
Veröffentlicht: (2024)

Shortest Paths in Multimode Graphs
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2025)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
von: Bodwin, Greg, et al.
Veröffentlicht: (2022)

Improved space-time tradeoff for TSP via extremal set systems
von: Dallant, Justin, et al.
Veröffentlicht: (2026)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

Verifying Shortest Paths in Linear Time
von: Shokry, Ahmed, et al.
Veröffentlicht: (2024)

Hierarchical Multicriteria Shortest Path Search
von: Kurbanov, Temirlan, et al.
Veröffentlicht: (2025)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

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

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
von: Chen, Yeyuan
Veröffentlicht: (2024)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)