scientific article; zbMATH DE number 7378686
From MaRDI portal
Publication:5009573
DOI10.4230/LIPIcs.ESA.2018.16MaRDI QIDQ5009573
Paweł Gawrychowski, Oren Weimann, Shay Mozes, Hsien-Chih Chang
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1807.01478
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Graph spanners: a tutorial review ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Semi-local string comparison: algorithmic techniques and applications
- Geometric applications of a matrix-searching algorithm
- Sublinear-space distance labeling using hubs
- Unified compression-based acceleration of edit-distance computation
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Preserving Terminal Distances Using Minors
- Vertex Sparsification in Trees
- An Almost Linear Time Algorithm for Generalized Matrix Searching
- Sparse Sourcewise and Pairwise Distance Preservers
- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
- Succinct Representations of Separable Graphs
- Short path queries in planar graphs in constant time
- Spanners and emulators with sublinear distance errors
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Lower-Stretch Spanning Trees
- Implicat Representation of Graphs
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Simpler, faster and shorter labels for distances in graphs
- Error Amplification for Pairwise Spanner Lower Bounds
- Better Distance Preservers and Additive Spanners
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Linear Size Distance Preservers
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Sublinear Distance Labeling
- The 4/3 Additive Spanner Exponent Is Tight
- Testing subgraphs in large graphs
- Distance labeling in graphs
- All-Pairs Almost Shortest Paths
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
- On minimal n-universal graphs
- Improved algorithms for min cut and max flow in undirected planar graphs
- Sparse Distance Preservers and Additive Spanners
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Computing the Girth of a Planar Graph in Linear Time
- Vertex Sparsifiers: New Results from Old Techniques
- Many distances in planar graphs
This page was built for publication:
