Graph spanners: a tutorial review (Q2026289)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Graph spanners: a tutorial review	scientific article

Statements

scholarly article

0 references

Graph spanners: a tutorial review (English)

0 references

0 references

0 references

Faryad Darabi Sahneh

0 references

0 references

Mohammad Javad Latifi Jebelli

0 references

Stephen G. Kobourov

0 references

0 references

Computer Science Review

0 references

publication date

19 May 2021

0 references

full work available at URL

https://arxiv.org/abs/1909.03152

0 references

describes a project that uses

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

Complexity of network synchronization

0 references

Approximate distance oracles for geometric spanners

0 references

Geometric Spanner Networks

0 references

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

0 references

On sparse spanners of weighted graphs

0 references

Generating Sparse 2-Spanners

0 references

An Optimal Synchronizer for the Hypercube

0 references

There are planar graphs almost as good as the complete graph

0 references

0 references

Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners

0 references

0 references

Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s

0 references

Sur la trialité et certains groupes qui s'en déduisent

0 references

NP-completeness of minimum spanner problems

0 references

0 references

Approximating \(k\)-spanner problems for \(k>2\)

0 references

The hardness of approximating spanner problems

0 references

Label Cover Instances with Large Girth and the Hardness of Approximating Basic <i>k</i> -Spanner

0 references

0 references

0 references

NP-hardness and fixed-parameter tractability of the minimum spanner problem

0 references

Additive graph spanners

0 references

The Greedy Spanner is Existentially Optimal

0 references

Additive Spanners: A Simple Construction

0 references

A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees

0 references

Distributed Computing: A Locality-Sensitive Approach

0 references

Greedy spanners are optimal in doubling metrics

0 references

NEW SPARSENESS RESULTS ON GRAPH SPANNERS

0 references

0 references

Fast Constructions of Lightweight Spanners for General Graphs

0 references

Near-Optimal Light Spanners

0 references

Additive spanners and (α, β)-spanners

0 references

Low distortion spanners

0 references

On Pairwise Spanners

0 references

Small Stretch Pairwise Spanners

0 references

New pairwise spanners

0 references

Spanners and emulators with sublinear distance errors

0 references

0 references

Better Distance Preservers and Additive Spanners

0 references

$(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs

0 references

0 references

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

0 references

New Additive Spanners

0 references

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

0 references

Sparse Distance Preservers and Additive Spanners

0 references

Sparse Sourcewise and Pairwise Distance Preservers

0 references

Error Amplification for Pairwise Spanner Lower Bounds

0 references

Linear Size Distance Preservers

0 references

Distance-Preserving Subgraphs of Interval Graphs

0 references

On the Structure of Unique Shortest Paths in Graphs

0 references

The 4/3 Additive Spanner Exponent Is Tight

0 references

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

0 references

Terminal embeddings

0 references

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

0 references

0 references

Additive Spanners in Nearly Quadratic Time

0 references

0 references

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

0 references

New (<i>α, β</i>) Spanners and Hopsets

0 references

Thorup-Zwick emulators are universally optimal hopsets

0 references

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

0 references

Algorithms – ESA 2004

0 references

Directed spanners via flow-based linear programs

0 references

Approximation algorithms for spanner problems and directed Steiner forest

0 references

0 references

Approximating Low-Stretch Spanners

0 references

Computing almost shortest paths

0 references

Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models

0 references

Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

0 references

On the locality of distributed sparse spanner construction

0 references

Streaming algorithm for graph spanners-single pass and constant processing time per edge

0 references

Distributed algorithms for ultrasparse spanners and linear size skeletons

0 references

Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners

0 references

Efficient distributed source detection with limited bandwidth

0 references

Spanners and sparsifiers in dynamic streams

0 references

Distributed construction of purely additive spanners

0 references

The sparsest additive spanner via multiple weighted BFS trees

0 references

Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

0 references

On graph problems in a semi-streaming model

0 references

0 references

All-Pairs Almost Shortest Paths

0 references

0 references

Approximate distance oracles

0 references

Automata, Languages and Programming

0 references

Approximate distance oracles for unweighted graphs in expected <i>O</i> ( <i>n</i> <sup>2</sup> ) time

0 references

Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error

0 references

Shortest-path queries in static networks

0 references

Towards tight approximation bounds for graph diameter and eccentricities

0 references

Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

0 references

Ramsey Spanning Trees and Their Applications

0 references

Spanners with Slack

0 references

Spanners in sparse graphs

0 references

0 references

0 references

Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs

0 references

Mixed-integer programming approaches for the tree \(t^*\)-spanner problem

0 references

Generating Low-Degree 2-Spanners

0 references

0 references

Optimal Euclidean Spanners

0 references

New Doubling Spanners: Better and Simpler

0 references

Fault Tolerant Spanners for General Graphs

0 references

COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING

0 references

Fault-tolerant spanners

0 references

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

0 references

Improved Purely Additive Fault-Tolerant Spanners

0 references

Vertex fault tolerant additive spanners

0 references

A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

0 references

0 references

Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

0 references

Sparse Fault-Tolerant BFS Trees

0 references

Dual Failure Resilient BFS Structure

0 references

Multiple Source Dual Fault Tolerant BFS Trees

0 references

0 references

On resilient graph spanners

0 references

Small Stretch Spanners on Dynamic Graphs

0 references

Dynamic Algorithms for Graph Spanners

0 references

Fully dynamic randomized algorithms for graph spanners

0 references

0 references

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching

0 references

0 references

Improved Approximation for the Directed Spanner Problem

0 references

Source-wise round-trip spanners

0 references

Deterministic improved round-trip spanners

0 references

Polylog-time and near-linear work approximation scheme for undirected shortest paths

0 references

Concurrent counting is harder than queuing

0 references

Computing Visibility Information in an Inaccurate Simple Polygon

0 references

Reconstructing the shape of a tree from observed dissimilarity data

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/j.cosrev.2020.100253

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2026289

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