Deterministic fault-tolerant connectivity labeling scheme
From MaRDI portal
Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)
Cites work
- (1 + )-approximate f-sensitive distance oracles
- -nets and simplex range queries
- \(f\)-sensitivity distance oracles and routing schemes
- A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
- A nearly optimal oracle for avoiding failed vertices and edges
- A simple proof of optimal epsilon nets
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Compact and fast sensitivity oracles for single-source distances
- Compact Forbidden-Set Routing
- Connectivity oracles for failure prone graphs
- Connectivity oracles for graphs subject to vertex failures
- Constrained-path labellings on graphs of bounded clique-width
- Construction and impromptu repair of an MST in a distributed network with o(m) communication
- Derandomization in Computational Geometry
- Distributed MST and broadcast with fewer messages, and faster gossiping
- Dual-failure distance and connectivity oracles
- Dynamic graph connectivity in polylogarithmic worst case time
- Efficient oracles and routing schemes for replacement paths
- Fast computation of small cuts via cycle space sampling
- Faster deterministic fully-dynamic graph connectivity
- Faster replacement paths and distance sensitivity oracles
- Fault-Tolerant Compact Routing Schemes for General Graphs
- Fault-tolerant distance labeling for planar graphs
- Fault-Tolerant Labeling and Compact Routing Schemes
- Forbidden-set distance labels for graphs of bounded doubling dimension
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
- scientific article; zbMATH DE number 2119745 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- Implicat Representation of Graphs
- Logarithmic Lower Bounds in the Cell-Probe Model
- MST in \(O(1)\) rounds of congested clique
- MST in log-star rounds of congested clique
- Near-optimal fully-dynamic graph connectivity
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Single pass spectral sparsification in dynamic streams
- Space efficient edge-fault tolerant routing
- Spanners and sparsifiers in dynamic streams
- Subjective-cost policy routing
- Time-message trade-offs in distributed algorithms
- Toward optimal bounds in the congested clique, graph connectivity and MST
This page was built for publication: Deterministic fault-tolerant connectivity labeling scheme
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7004077)
