Connectivity oracles for graphs subject to vertex failures
From MaRDI portal
Publication:3387763
Recommendations
Cites work
- scientific article; zbMATH DE number 6381684 (Why is no real title available?)
- scientific article; zbMATH DE number 1263227 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
- A linear-time algorithm for a special case of disjoint set union
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A nearly optimal oracle for avoiding failed vertices and edges
- Adaptive and approximate orthogonal range counting
- An improved algorithm for incremental DFS tree in undirected graphs
- An optimal dual fault tolerant reachability oracle
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Bounded degree spanning trees (extended abstract)
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Concentration of Measure for the Analysis of Randomized Algorithms
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- Connectivity Oracles for Planar Graphs
- Connectivity oracles for failure prone graphs
- Connectivity oracles for graphs subject to vertex failures
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Design and implementation of an efficient priority queue
- Dual-failure distance and connectivity oracles
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic Subgraph Connectivity with Geometric Applications
- Dynamic connectivity: connecting to networks and geometry
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamically switching vertices in planar graphs
- Expander flows, geometric embeddings and graph partitioning
- Faster Online Matrix-Vector Multiplication
- Faster deterministic fully-dynamic graph connectivity
- Faster randomized worst-case update time for dynamic subgraph connectivity
- Faster worst case deterministic dynamic connectivity
- Fault Tolerant Approximate BFS Structures
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Fault tolerant additive spanners
- Fault tolerant spanners for general graphs
- Fault tolerant subgraph for single source reachability: generic and optimal
- Fault-tolerant logical network structures
- Fault-tolerant spanners
- 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
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Higher lower bounds from the 3SUM conjecture
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Improved purely additive fault-tolerant spanners
- Improved subquadratic 3SUM
- Incremental and fully dynamic subgraph connectivity for emergency planning
- Maintaining bridge-connected and biconnected components on-line
- Maintaining the 3-Edge-Connected Components of a Graph On-Line
- Maintaining the classes of 4-edge-connectivity in a graph on-line
- Maintenance of 2- and 3-edge-connected components of graphs. I
- Near-optimal range reporting structures for categorical data
- New data structures for subgraph connectivity
- On-line maintenance of triconnected components with SPQR-trees
- Oracles for Distances Avoiding a Failed Node or Link
- Orthogonal range searching on the RAM, revisited
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Single source distance oracle for planar digraphs avoiding a failed node or link
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Sparse fault-tolerant BFS trees
- Sparsification—a technique for speeding up dynamic graph algorithms
- Subquadratic algorithms for 3SUM
- The level ancestor problem simplified
- Threesomes, degenerates, and love triangles
- Time-space trade-offs for predecessor search
- Trees in Polyhedral Graphs
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- \(f\)-sensitivity distance oracles and routing schemes
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)
