Deterministic replacement path covering

DOI10.1145/3673760MaRDI QIDQ7023539zbMATH OpenFDO

Authors C. S. Karthik, M. Parter

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3673760

zbMATH Keywords

deterministic algorithmsdistance sensitivity oraclesfault-tolerant graph algorithmsspanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Cites work

• (1 + )-approximate f-sensitive distance oracles
• A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound
• Algorithmic construction of sets for k -restrictions
• Balanced families of perfect hash functions and their applications
• Color-coding
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Dual failure resilient BFS structure
• Efficient and Simple Algorithms for Fault-Tolerant Spanners
• Explicit construction of exponential sized families of k-independent sets
• Explicit constructions of perfect hash families from algebraic curves over finite fields
• Faster replacement paths and distance sensitivity oracles
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Fault tolerant spanners for general graphs
• Fault-tolerant spanners
• scientific article; zbMATH DE number 3458474 (Why is no real title available?)
• scientific article; zbMATH DE number 1256708 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Low congestion cycle covers and their applications
• Maximum distance<tex>q</tex>-nary codes
• Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
• On the asymptotic behaviour of some towers of function fields over finite fields
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Perfect Hashing and Probability
• Polynomial Codes Over Certain Finite Fields
• Recursive bounds for perfect hashing
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Secure Distributed Computing Made (Nearly) Optimal
• Sensitive distance and reachability oracles for large batch updates
• Small cuts and connectivity certificates: a fault tolerant approach
• Sparse Fault-Tolerant BFS Structures
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Spatial Complexity of Oblivious k-Probe Hash Functions

This page was built for publication: Deterministic replacement path covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023539)