Buchumschlag

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chi, Shucheng, Duan, Ran, Wang, Benyu, Xie, Tianle
Format:	Preprint
Veröffentlicht:	2024
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

Undirected Replacement Paths: Dual Fault Reduces to Single Source
von: Nogler, Jakob, et al.
Veröffentlicht: (2026)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
von: Yan, Shuyi
Veröffentlicht: (2025)

Sandpile Prediction on Undirected Graphs
von: Chang, Ruinian, et al.
Veröffentlicht: (2023)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

Network Design on Undirected Series-Parallel Graphs
von: Bansal, Ishan, et al.
Veröffentlicht: (2024)

Personalized PageRank Estimation in Undirected Graphs
von: Bertram, Christian, et al.
Veröffentlicht: (2026)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
von: Wang, Hanzhi
Veröffentlicht: (2024)

Simpler and Improved Replacement Path Coverings
von: Bilò, Davide, et al.
Veröffentlicht: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
von: Chechik, Shiri, et al.
Veröffentlicht: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
von: Fischer, Olivier, et al.
Veröffentlicht: (2025)

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

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Nearly Optimal Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2022)

Time To Replace Your Filter: How Maplets Simplify System Design
von: Bender, Michael A., et al.
Veröffentlicht: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
von: Jiang, Tianle, et al.
Veröffentlicht: (2024)

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

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

Approximating Partition in Near-Linear Time
von: Chen, Lin, et al.
Veröffentlicht: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
von: Das, Debarati, et al.
Veröffentlicht: (2026)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
von: Bodwin, Greg, et al.
Veröffentlicht: (2023)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

A Nearly Quadratic-Time FPTAS for Knapsack
von: Chen, Lin, et al.
Veröffentlicht: (2023)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
von: Kosinas, Evangelos
Veröffentlicht: (2025)

Optimal Distributed Replacement Paths
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
von: Parter, Merav, et al.
Veröffentlicht: (2025)

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
von: Liu, Yuxi, et al.
Veröffentlicht: (2026)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
von: Roditty, Liam, et al.
Veröffentlicht: (2026)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
von: Mao, Xiao
Veröffentlicht: (2023)