Sparsification lower bound for linear spanners in directed graphs
From MaRDI portal
Publication:2055974
DOI10.1016/j.tcs.2021.10.022zbMath1478.68264arXiv2203.08601OpenAlexW3208948601MaRDI QIDQ2055974
Publication date: 1 December 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.08601
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Best-case and worst-case sparsifiability of Boolean CSPs
- On sparse spanners of weighted graphs
- NP-completeness of minimum spanner problems
- Which problems have strongly exponential complexity?
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Graph spanners: a tutorial review
- On sparsification for computing treewidth
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Additive Spanners: A Simple Construction
- Additive spanners and (α, β)-spanners
- Spanners and emulators with sublinear distance errors
- Additive Spanners in Nearly Quadratic Time
- Graph spanners
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Sparsification—a technique for speeding up dynamic graph algorithms
- The 4/3 Additive Spanner Exponent Is Tight
- Kernelization
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Additive graph spanners
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- New Additive Spanners
