Connectivity Oracles for Graphs Subject to Vertex Failures (Q3387763): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
+Normal rank
@@ Property / cites work @@
+Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
+Normal rank
@@ Property / cites work @@
+Q5743413
@@ Property / cites work: Q5743413 / rank @@
+Normal rank
@@ Property / cites work @@
+$O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
+Normal rank
@@ Property / cites work @@
+Expander flows, geometric embeddings and graph partitioning
+Normal rank
@@ Property / cites work @@
+Subquadratic algorithms for 3SUM
@@ Property / cites work: Subquadratic algorithms for 3SUM / rank @@
+Normal rank
@@ Property / cites work @@
+Trees in Polyhedral Graphs
@@ Property / cites work: Trees in Polyhedral Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743393
@@ Property / cites work: Q5743393 / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic DFS in Undirected Graphs: breaking the O(<i>m</i>) barrier
+Normal rank
@@ Property / cites work @@
+Fault tolerant subgraph for single source reachability: generic and optimal
+Normal rank
@@ Property / cites work @@
+On-line maintenance of triconnected components with SPQR-trees
+Normal rank
@@ Property / cites work @@
+Q4508365
@@ Property / cites work: Q4508365 / rank @@
+Normal rank
@@ Property / cites work @@
+The level ancestor problem simplified
@@ Property / cites work: The level ancestor problem simplified / rank @@
+Normal rank
@@ Property / cites work @@
+A nearly optimal oracle for avoiding failed vertices and edges
+Normal rank
@@ Property / cites work @@
+Improved Purely Additive Fault-Tolerant Spanners
@@ Property / cites work: Improved Purely Additive Fault-Tolerant Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Connectivity Oracles for Planar Graphs
@@ Property / cites work: Connectivity Oracles for Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Fault Tolerant Additive Spanners
@@ Property / cites work: Fault Tolerant Additive Spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Fault tolerant additive and \((\mu, \alpha)\)-spanners
+Normal rank
@@ Property / cites work @@
+Dynamic Subgraph Connectivity with Geometric Applications
+Normal rank
@@ Property / cites work @@
+Orthogonal range searching on the RAM, revisited
@@ Property / cites work: Orthogonal range searching on the RAM, revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic Connectivity: Connecting to Networks and Geometry
+Normal rank
@@ Property / cites work @@
+Adaptive and Approximate Orthogonal Range Counting
+Normal rank
@@ Property / cites work @@
+Fault Tolerant Spanners for General Graphs
@@ Property / cites work: Fault Tolerant Spanners for General Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+\(f\)-sensitivity distance oracles and routing schemes
+Normal rank
@@ Property / cites work @@
+Q5116480
@@ Property / cites work: Q5116480 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ Property / cites work @@
+Finding Connected Components in O(log n log log n) Time on the EREW PRAM
+Normal rank
@@ Property / cites work @@
+Q4598272
@@ Property / cites work: Q4598272 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded degree spanning trees (extended abstract)
@@ Property / cites work: Bounded degree spanning trees (extended abstract) / rank @@
+Normal rank
@@ Property / cites work @@
+Oracles for Distances Avoiding a Failed Node or Link
+Normal rank
@@ Property / cites work @@
+Fault-tolerant spanners
@@ Property / cites work: Fault-tolerant spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234099
@@ Property / cites work: Q4234099 / rank @@
+Normal rank
@@ Property / cites work @@
+Maintaining the classes of 4-edge-connectivity in a graph on-line
+Normal rank
@@ Property / cites work @@
+New Data Structures for Subgraph Connectivity
@@ Property / cites work: New Data Structures for Subgraph Connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4633861
@@ Property / cites work: Q4633861 / rank @@
+Normal rank
@@ Property / cites work @@
+Connectivity oracles for failure prone graphs
@@ Property / cites work: Connectivity oracles for failure prone graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Connectivity Oracles for Graphs Subject to Vertex Failures
+Normal rank
@@ Property / cites work @@
+Faster randomized worst-case update time for dynamic subgraph connectivity
+Normal rank
@@ Property / cites work @@
+Concentration of Measure for the Analysis of Randomized Algorithms
+Normal rank
@@ Property / cites work @@
+Sparsification—a technique for speeding up dynamic graph algorithms
+Normal rank
@@ Property / cites work @@
+Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
+Normal rank
@@ Property / cites work @@
+Improved subquadratic 3SUM
@@ Property / cites work: Improved subquadratic 3SUM / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamically switching vertices in planar graphs
@@ Property / cites work: Dynamically switching vertices in planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the Minimum-Degree Steiner Tree to within One of Optimal
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for a special case of disjoint set union
+Normal rank
@@ Property / cites work @@
+Maintaining the 3-Edge-Connected Components of a Graph On-Line
+Normal rank
@@ Property / cites work @@
+Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
+Normal rank
@@ Property / cites work @@
+Threesomes, Degenerates, and Love Triangles
@@ Property / cites work: Threesomes, Degenerates, and Love Triangles / rank @@
+Normal rank
@@ Property / cites work @@
+Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
+Normal rank
@@ Property / cites work @@
+Q4606319
@@ Property / cites work: Q4606319 / rank @@
+Normal rank
@@ Property / cites work @@
+Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Connectivity in <i>O</i>(log <i>n</i>(log log <i>n</i>)<sup>2</sup>) Amortized Expected Time
+Normal rank
@@ Property / cites work @@
+Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
+Normal rank
@@ Property / cites work @@
+Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
+Normal rank
@@ Property / cites work @@
+Dynamic graph connectivity in polylogarithmic worst case time
+Normal rank
@@ Property / cites work @@
+Faster worst case deterministic dynamic connectivity
+Normal rank
@@ Property / cites work @@
+Higher Lower Bounds from the 3SUM Conjecture
@@ Property / cites work: Higher Lower Bounds from the 3SUM Conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Near-Optimal Range Reporting Structures for Categorical Data
+Normal rank
@@ Property / cites work @@
+Faster Online Matrix-Vector Multiplication
@@ Property / cites work: Faster Online Matrix-Vector Multiplication / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
+Normal rank
@@ Property / cites work @@
+Q4967205
@@ Property / cites work: Q4967205 / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse Fault-Tolerant BFS Trees
@@ Property / cites work: Sparse Fault-Tolerant BFS Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Fault Tolerant Approximate BFS Structures
@@ Property / cites work: Fault Tolerant Approximate BFS Structures / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space trade-offs for predecessor search
@@ Property / cites work: Time-space trade-offs for predecessor search / rank @@
+Normal rank
@@ Property / cites work @@
+A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
+Normal rank
@@ Property / cites work @@
+Maintenance of 2- and 3-edge-connected components of graphs. I
+Normal rank
@@ Property / cites work @@
+Q2934638
@@ Property / cites work: Q2934638 / rank @@
+Normal rank
@@ Property / cites work @@
+Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
+Normal rank
@@ Property / cites work @@
+Design and implementation of an efficient priority queue
+Normal rank
@@ Property / cites work @@
+Maintaining bridge-connected and biconnected components on-line
+Normal rank
@@ Property / cites work @@
+Faster Deterministic Fully-Dynamic Graph Connectivity
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/17m1146610
+Normal rank
@@ Property / OpenAlex ID @@
+W3112502550
@@ Property / OpenAlex ID: W3112502550 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:3387763