Connectivity Oracles for Graphs Subject to Vertex Failures (Q3387763)

From MaRDI portal

Revision as of 08:35, 24 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Connectivity Oracles for Graphs Subject to Vertex Failures	scientific article

Statements

scholarly article

0 references

Connectivity Oracles for Graphs Subject to Vertex Failures (English)

0 references

zbMATH Open document ID

0 references

10.1137/17M1146610

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

13 January 2021

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

zbMATH Keywords

graph connecitivity

0 references

dynamic graph

0 references

graph sketching

0 references

Steiner tree

0 references

MaRDI profile type

MaRDI publication profile

0 references

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

0 references

Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension

0 references

0 references

$O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time

0 references

Expander flows, geometric embeddings and graph partitioning

0 references

Subquadratic algorithms for 3SUM

0 references

Trees in Polyhedral Graphs

0 references

0 references

Dynamic DFS in Undirected Graphs: breaking the O(<i>m</i>) barrier

0 references

Fault tolerant subgraph for single source reachability: generic and optimal

0 references

On-line maintenance of triconnected components with SPQR-trees

0 references

0 references

The level ancestor problem simplified

0 references

A nearly optimal oracle for avoiding failed vertices and edges

0 references

Improved Purely Additive Fault-Tolerant Spanners

0 references

Connectivity Oracles for Planar Graphs

0 references

Fault Tolerant Additive Spanners

0 references

Fault tolerant additive and \((\mu, \alpha)\)-spanners

0 references

Dynamic Subgraph Connectivity with Geometric Applications

0 references

Orthogonal range searching on the RAM, revisited

0 references

Dynamic Connectivity: Connecting to Networks and Geometry

0 references

Adaptive and Approximate Orthogonal Range Counting

0 references

Fault Tolerant Spanners for General Graphs

0 references

\(f\)-sensitivity distance oracles and routing schemes

0 references

0 references

Approximation algorithms for metric facility location and <i>k</i> -Median problems using the primal-dual schema and Lagrangian relaxation

0 references

Finding Connected Components in O(log n log log n) Time on the EREW PRAM

0 references

0 references

Bounded degree spanning trees (extended abstract)

0 references

Oracles for Distances Avoiding a Failed Node or Link

0 references

Fault-tolerant spanners

0 references

0 references

Maintaining the classes of 4-edge-connectivity in a graph on-line

0 references

New Data Structures for Subgraph Connectivity

0 references

0 references

Connectivity oracles for failure prone graphs

0 references

Connectivity Oracles for Graphs Subject to Vertex Failures

0 references

Faster randomized worst-case update time for dynamic subgraph connectivity

0 references

Concentration of Measure for the Analysis of Randomized Algorithms

0 references

Sparsification—a technique for speeding up dynamic graph algorithms

0 references

Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications

0 references

Improved subquadratic 3SUM

0 references

Dynamically switching vertices in planar graphs

0 references

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

0 references

A linear-time algorithm for a special case of disjoint set union

0 references

Maintaining the 3-Edge-Connected Components of a Graph On-Line

0 references

Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

0 references

Threesomes, Degenerates, and Love Triangles

0 references

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

0 references

0 references

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

0 references

Fully Dynamic Connectivity in <i>O</i>(log <i>n</i>(log log <i>n</i>)<sup>2</sup>) Amortized Expected Time

0 references

Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

0 references

Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM

0 references

Dynamic graph connectivity in polylogarithmic worst case time

0 references

Faster worst case deterministic dynamic connectivity

0 references

Higher Lower Bounds from the 3SUM Conjecture

0 references

Near-Optimal Range Reporting Structures for Categorical Data

0 references

Faster Online Matrix-Vector Multiplication

0 references

A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph

0 references

0 references

Sparse Fault-Tolerant BFS Trees

0 references

Fault Tolerant Approximate BFS Structures

0 references

Time-space trade-offs for predecessor search

0 references

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

0 references

Maintenance of 2- and 3-edge-connected components of graphs. I

0 references

0 references

Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut

0 references

Design and implementation of an efficient priority queue

0 references

Maintaining bridge-connected and biconnected components on-line

0 references

Faster Deterministic Fully-Dynamic Graph Connectivity

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3387763

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3387763&oldid=36644535"