Imagen de Portada

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chi, Shucheng, Duan, Ran, Wang, Benyu, Xie, Tianle
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Undirected Replacement Paths: Dual Fault Reduces to Single Source
por: Nogler, Jakob, et al.
Publicado: (2026)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

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

Sandpile Prediction on Undirected Graphs
por: Chang, Ruinian, et al.
Publicado: (2023)

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

Network Design on Undirected Series-Parallel Graphs
por: Bansal, Ishan, et al.
Publicado: (2024)

Personalized PageRank Estimation in Undirected Graphs
por: Bertram, Christian, et al.
Publicado: (2026)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
por: Wang, Hanzhi
Publicado: (2024)

Simpler and Improved Replacement Path Coverings
por: Bilò, Davide, et al.
Publicado: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
por: Jiang, Yonggang, et al.
Publicado: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
por: Chechik, Shiri, et al.
Publicado: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
por: Fischer, Olivier, et al.
Publicado: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
por: Bernstein, Aaron, et al.
Publicado: (2022)

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

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

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
por: Bhanja, Koustav, et al.
Publicado: (2025)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
por: Manoharan, Vignesh, et al.
Publicado: (2022)

Time To Replace Your Filter: How Maplets Simplify System Design
por: Bender, Michael A., et al.
Publicado: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
por: Jiang, Tianle, et al.
Publicado: (2024)

Verifying Shortest Paths in Linear Time
por: Shokry, Ahmed, et al.
Publicado: (2024)

Vizing's Theorem in Near-Linear Time
por: Assadi, Sepehr, et al.
Publicado: (2024)

Approximating Partition in Near-Linear Time
por: Chen, Lin, et al.
Publicado: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
por: Henzinger, Monika, et al.
Publicado: (2024)

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

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

0-1 Knapsack in Nearly Quadratic Time
por: Jin, Ce
Publicado: (2023)

Improved Tree Sparsifiers in Near-Linear Time
por: Agassy, Daniel, et al.
Publicado: (2025)

A Nearly Quadratic-Time FPTAS for Knapsack
por: Chen, Lin, et al.
Publicado: (2023)

Knapsack with Small Items in Near-Quadratic Time
por: Bringmann, Karl
Publicado: (2023)

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

Optimal Distributed Replacement Paths
por: Chang, Yi-Jun, et al.
Publicado: (2025)

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

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
por: Parter, Merav, et al.
Publicado: (2025)

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

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
por: Roditty, Liam, et al.
Publicado: (2026)

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

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
por: Fischer, Nick, et al.
Publicado: (2024)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
por: Mao, Xiao
Publicado: (2023)