Conditional hardness for sensitivity problems
From MaRDI portal
Recommendations
- On the hardness of partially dynamic graph problems and connections to diameter
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Improved distance sensitivity oracles with subcubic preprocessing time
- Compact and fast sensitivity oracles for single-source distances
- Faster replacement paths and distance sensitivity oracles
Cites work
- (1 + )-approximate f-sensitive distance oracles
- \(f\)-sensitivity distance oracles and routing schemes
- A faster computation of the most vital edge of a shortest path
- A nearly optimal oracle for avoiding failed vertices and edges
- An optimal dual fault tolerant reachability oracle
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Automata, Languages and Programming
- Compact and fast sensitivity oracles for single-source distances
- Connectivity oracles for failure prone graphs
- Connectivity oracles for graphs subject to vertex failures
- Dual failure resilient BFS structure
- Dual-failure distance and connectivity oracles
- Faster replacement paths
- Fault tolerant additive spanners
- Fault Tolerant Approximate BFS Structures
- Fault tolerant reachability for directed graphs
- Fault tolerant subgraph for single source reachability: generic and optimal
- Fault-tolerant approximate shortest-path trees
- Finding a Minimum Circuit in a Graph
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- Improved purely additive fault-tolerant spanners
- Incremental and fully dynamic subgraph connectivity for emergency planning
- Matching triangles and basing hardness on an extremely popular conjecture
- More algorithms for all-pairs shortest paths in weighted graphs
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Multiplying matrices faster than coppersmith-winograd
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On the complexity of k-SAT
- On the hardness of partially dynamic graph problems and connections to diameter
- Powers of tensors and fast matrix multiplication
- Replacement paths and k simple shortest paths in unweighted directed graphs
- Single source distance oracle for planar digraphs avoiding a failed node or link
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subcubic equivalences between path, matrix, and triangle problems
- Towards polynomial lower bounds for dynamic problems
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Which problems have strongly exponential complexity?
Cited in
(10)- On the hardness of partially dynamic graph problems and connections to diameter
- Algorithms and hardness for diameter in dynamic graphs
- Strong connectivity in directed graphs under failures, with applications
- Range updates and range sum queries on multidimensional points with monoid weights
- Fine-Grained Complexity of Regular Path Queries
- How fast can we play Tetris greedily with rectangular pieces?
- Conditional lower bounds for dynamic geometric measure problems
- Conditional lower bounds for dynamic geometric measure problems
- Fine-grained complexity of regular path queries
- Fault-tolerant ST-diameter oracles
This page was built for publication: Conditional hardness for sensitivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638076)
