scientific article; zbMATH DE number 6866316

DOI10.4230/LIPIcs.ITCS.2017.26zbMath1402.68075arXiv1703.01638MaRDI QIDQ4638076

Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams, Monika R. Henzinger

Publication date: 3 May 2018

Full work available at URL: https://arxiv.org/abs/1703.01638

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

sensitivitydata structuresdynamic graph algorithmsconditional lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Range updates and range sum queries on multidimensional points with monoid weights ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• A faster computation of the most vital edge of a shortest path
• Which problems have strongly exponential complexity?
• Fault tolerant reachability for directed graphs
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Dual Failure Resilient BFS Structure
• Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
• Connectivity oracles for failure prone graphs
• Towards polynomial lower bounds for dynamic problems
• Fault-Tolerant Approximate Shortest-Path Trees
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Powers of tensors and fast matrix multiplication
• Improved Purely Additive Fault-Tolerant Spanners
• More algorithms for all-pairs shortest paths in weighted graphs
• Finding a Minimum Circuit in a Graph
• Higher Lower Bounds from the 3SUM Conjecture
• Connectivity Oracles for Graphs Subject to Vertex Failures
• (1 + ∊)-Approximate f-Sensitive Distance Oracles
• On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Compact and Fast Sensitivity Oracles for Single-Source Distances
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• A nearly optimal oracle for avoiding failed vertices and edges
• Fault Tolerant Additive Spanners
• Fault tolerant subgraph for single source reachability: generic and optimal
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Fault Tolerant Approximate BFS Structures
• Multiplying matrices faster than coppersmith-winograd
• Automata, Languages and Programming
• On the complexity of \(k\)-SAT