Connectivity oracles for graphs subject to vertex failures
From MaRDI portal
Publication:3387763
DOI10.1137/17M1146610zbMATH Open1467.68139OpenAlexW3112502550MaRDI QIDQ3387763FDOQ3387763
Authors: Ran Duan, Seth Pettie 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)
Cites Work
- Subquadratic algorithms for 3SUM
- Oracles for Distances Avoiding a Failed Node or Link
- Title not available (Why is that?)
- Threesomes, degenerates, and love triangles
- A nearly optimal oracle for avoiding failed vertices and edges
- Expander flows, geometric embeddings and graph partitioning
- The level ancestor problem simplified
- \(f\)-sensitivity distance oracles and routing schemes
- A linear-time algorithm for a special case of disjoint set union
- Time-space trade-offs for predecessor search
- Adaptive and approximate orthogonal range counting
- Orthogonal range searching on the RAM, revisited
- Concentration of Measure for the Analysis of Randomized Algorithms
- Fault-tolerant spanners
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Fault tolerant additive spanners
- Fault tolerant spanners for general graphs
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Design and implementation of an efficient priority queue
- Sparsification—a technique for speeding up dynamic graph algorithms
- Near-optimal range reporting structures for categorical data
- Bounded degree spanning trees (extended abstract)
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Trees in Polyhedral Graphs
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- On-line maintenance of triconnected components with SPQR-trees
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Improved subquadratic 3SUM
- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
- Maintaining bridge-connected and biconnected components on-line
- Dynamic Subgraph Connectivity with Geometric Applications
- Maintaining the 3-Edge-Connected Components of a Graph On-Line
- Maintenance of 2- and 3-edge-connected components of graphs. I
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Sparse fault-tolerant BFS trees
- Connectivity oracles for failure prone graphs
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Improved purely additive fault-tolerant spanners
- Connectivity oracles for graphs subject to vertex failures
- Dual-failure distance and connectivity oracles
- Fault tolerant subgraph for single source reachability: generic and optimal
- Dynamic graph connectivity in polylogarithmic worst case time
- Title not available (Why is that?)
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Fault-tolerant logical network structures
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Finding Connected Components in O(log n log log n) Time on the EREW PRAM
- Faster deterministic fully-dynamic graph connectivity
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Dynamic connectivity: connecting to networks and geometry
- Title not available (Why is that?)
- Dynamically switching vertices in planar graphs
- Title not available (Why is that?)
- Faster worst case deterministic dynamic connectivity
- Higher lower bounds from the 3SUM conjecture
- Fault Tolerant Approximate BFS Structures
- Faster Online Matrix-Vector Multiplication
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Faster randomized worst-case update time for dynamic subgraph connectivity
- An improved algorithm for incremental DFS tree in undirected graphs
- Forbidden-set distance labels for graphs of bounded doubling dimension
- Connectivity Oracles for Planar Graphs
- New data structures for subgraph connectivity
- An optimal dual fault tolerant reachability oracle
- Incremental and fully dynamic subgraph connectivity for emergency planning
- Single source distance oracle for planar digraphs avoiding a failed node or link
Cited In (10)
- A nearly optimal oracle for avoiding failed vertices and edges
- Connectivity Oracles for Planar Graphs
- Connectivity oracles for graphs subject to vertex failures
- Dual-failure distance and connectivity oracles
- Network failure detection and graph connectivity
- Connectivity oracles for failure prone graphs
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- On the time-space complexity of reachability queries for preprocessed graphs
- Network Failure Detection and Graph Connectivity
- 2-fault-tolerant strong connectivity oracles
This page was built for publication: Connectivity oracles for graphs subject to vertex failures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387763)
