Connectivity Oracles for Graphs Subject to Vertex Failures
From MaRDI portal
Publication:3387763
DOI10.1137/17M1146610zbMath1467.68139OpenAlexW3112502550MaRDI QIDQ3387763
Publication date: 13 January 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1146610
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved subquadratic 3SUM
- The level ancestor problem simplified
- Maintenance of 2- and 3-edge-connected components of graphs. I
- \(f\)-sensitivity distance oracles and routing schemes
- Bounded degree spanning trees (extended abstract)
- A linear-time algorithm for a special case of disjoint set union
- Maintaining bridge-connected and biconnected components on-line
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Dynamically switching vertices in planar graphs
- On-line maintenance of triconnected components with SPQR-trees
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Faster randomized worst-case update time for dynamic subgraph connectivity
- Subquadratic algorithms for 3SUM
- Sparse Fault-Tolerant BFS Trees
- Connectivity oracles for failure prone graphs
- Connectivity Oracles for Planar Graphs
- Time-space trade-offs for predecessor search
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fault-tolerant spanners
- Dynamic Connectivity: Connecting to Networks and Geometry
- $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
- Dynamic Subgraph Connectivity with Geometric Applications
- Improved Purely Additive Fault-Tolerant Spanners
- Oracles for Distances Avoiding a Failed Node or Link
- New Data Structures for Subgraph Connectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Maintaining the 3-Edge-Connected Components of a Graph On-Line
- Design and implementation of an efficient priority queue
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Sparsification—a technique for speeding up dynamic graph algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Threesomes, Degenerates, and Love Triangles
- Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
- Higher Lower Bounds from the 3SUM Conjecture
- Connectivity Oracles for Graphs Subject to Vertex Failures
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
- Faster Online Matrix-Vector Multiplication
- Faster worst case deterministic dynamic connectivity
- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
- Finding Connected Components in O(log n log log n) Time on the EREW PRAM
- Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
- Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- A nearly optimal oracle for avoiding failed vertices and edges
- Fault Tolerant Additive Spanners
- Fault tolerant subgraph for single source reachability: generic and optimal
- Fault Tolerant Approximate BFS Structures
- Fault Tolerant Spanners for General Graphs
- Orthogonal range searching on the RAM, revisited
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Trees in Polyhedral Graphs
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Adaptive and Approximate Orthogonal Range Counting
- Near-Optimal Range Reporting Structures for Categorical Data
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
- Concentration of Measure for the Analysis of Randomized Algorithms
- Expander flows, geometric embeddings and graph partitioning
