(1 + εΒ)-spanner constructions for general graphs

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Symposium on the Theory of Computing

• Publication date

  2001-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/380752.380797
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Hardness of Approximating Spanners

  2001cited by this paper
• Approximating k-Spanner Problems for k>2

  2001cited by this paper
• On the red-blue set cover problem

  2000cited by this paper
• Strong Inapproximability of the Basic k-Spanner Problem

  2000cited by this paper
• Designing Networks with Bounded Pairwise Distance

  1999cited by this paper
• Design networks with bounded pairwise distance

  1999cited by this paper
• The Client-Server 2-Spanner Problem with Applications to Network Design

  1999cited by this paper
• On the Hardness of Approximation Spanners

  1998cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• All pairs almost shortest paths

  1996influential reference
• On sparse spanners of weighted graphs

  1993cited by this paper
• Grid spanners

  1993cited by this paper
• Additive graph spanners

  1993cited by this paper
• New sparseness results on graph spanners

  1992cited by this paper
• Generating Sparse 2-Spanners

  1992cited by this paper
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems

  1992cited by this paper
• Graph Spanners: a Survey

  1992cited by this paper
• Extremal graphs with no C4's, C6's, or C10's

  1991cited by this paper
• Sparse partitions

  1990cited by this paper
• Delaunay graphs are almost as good as complete graphs

  1987cited by this paper
• Distributed Computing: A Locality-Sensitive Approach

  1987cited by this paper
• An optimal synchronizer for the hypercube

  1987cited by this paper
• There is a planar graph almost as good as the complete graph

  1986cited by this paper

• Simple Approximations for General Spanner Problems

  2025cites this paper
• Massively Parallel Algorithms for Approximate Shortest Paths

  2024cites this paper
• Lightweight Near-Additive Spanners

  2024cites this paper
• Almost-Optimal Sublinear Additive Spanners

  2023cites this paper
• Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.

  2022cites this paper
• (1+ε)-Approximate Shortest Paths in Dynamic Streams

  2022cites this paper
• Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

  2022cites this paper
• Bridge Girth: A Unifying Notion in Network Design

  2022cites this paper
• New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

  2022cites this paper
• New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

  2022cites this paper
• Exponentially Faster Shortest Paths in the Congested Clique

  2022cites this paper
• Fast Deterministic Fully Dynamic Distance Approximation

  2021cites this paper
• On Additive Spanners in Weighted Graphs with Local Error

  2021cites this paper
• Distributed Construction of Lightweight Spanners for Unit Ball Graphs

  2021cites this paper
• Sparsification lower bound for linear spanners in directed graphs

  2021cites this paper
• Fully polynomial time (Σ,Π)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\Sigma ,\Pi )$$\end{document}-approximatio

  2021cites this paper
• Weighted Sparse and Lightweight Spanners with Local Additive Error

  2021cites this paper
• Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product

  2021cites this paper
• A Fast Algorithm for Source-Wise Round-Trip Spanners

  2020cites this paper
• Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• Exponentially Faster Shortest Paths in the Congested Clique

  2020cites this paper
• A Polynomial Time Algorithm for Almost Optimal Vertex Fault Tolerant Spanners

  2020cites this paper
• Weighted Additive Spanners

  2020cites this paper
• On the Edge Crossings of the Greedy Spanner

  2020cites this paper
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

  2020cites this paper
• New algorithms and hardness for incremental single-source shortest paths in directed graphs

  2020cites this paper
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

  2020cites this paper
• Simple Distributed Spanners in Dense Congest Networks

  2020cites this paper
• SOFSEM 2020: Theory and Practice of Computer Science: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020, Proceedings

  2020influential citation
• Graph Spanners: A Tutorial Review

  2019cites this paper
• Distributed Construction of Light Networks

  2019cites this paper
• Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

  2019cites this paper
• Message Reduction in the LOCAL Model is a Free Lunch

  2019cites this paper
• Small Stretch Pairwise Spanners and D-spanners A Thesis Submitted to the Tata Institute of Fundamental Research, Mumbai for the degree of Master of Sciences in Computer Science by

  2019cites this paper
• An FPT Algorithm for Minimum Additive Spanner Problem

  2019cites this paper
• A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

  2018cites this paper
• Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

  2018cites this paper
• Diameter Spanner, Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant

  2018cites this paper
• A PTAS for subset TSP in minor-free graphs

  2018cites this paper
• Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts

  2018cites this paper
• Demand-aware network designs of bounded degree

  2017cites this paper
• Additive Spanners and Distance Oracles in Quadratic Time

  2017influential citation
• Minor-Free Graphs Have Light Spanners

  2017cites this paper
• Dynamic Shortest Path and Transitive Closure Algorithms: A Survey

  2017cites this paper
• Distance-preserving graph contractions

  2017cites this paper
• The 4/3 additive spanner exponent is tight

  2016cites this paper
• Distributed construction of purely additive spanners

  2016cites this paper
• Linear Size Distance Preservers

  2016cites this paper
• Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

  2016cites this paper
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners

  2016cites this paper
• Better Distance Preservers and Additive Spanners

  2015cites this paper
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

  2015cites this paper
• The 4/3 Additive Spanner Exponent Is Tight

  2015cites this paper
• 2 1 M ay 2 01 5 Better Distance Preservers and Additive Spanners Greg Bodwin

  2015cites this paper
• Vertex fault tolerant additive spanners

  2014cites this paper
• Bypassing Erdős' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners

  2014cites this paper
• Additive Spanners: A Simple Construction

  2014cites this paper
• Master ’ s Project Report Small Stretch Pairwise Spanners and D-spanners Student

  2014cites this paper
• Fault-Tolerant Approximate BFS Structures

  2014cites this paper
• New Additive Spanners

  2013cites this paper
• Network Design with Coverage Costs

  2013cites this paper
• HDLBR: A name-independent compact routing scheme for power-law networks

  2013cites this paper
• Efficient distributed source detection with limited bandwidth

  2013cites this paper
• Efficient Construction of Spanners in $d$-Dimensions

  2013influential citation
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

  2013cites this paper
• Routing Table Optimization using t-spanner Technique

  2013influential citation
• Fast Constructions of Lightweight Spanners for General Graphs

  2012cites this paper
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

  2012cites this paper
• Fast routing table construction using small messages: extended abstract

  2012cites this paper
• Multiplicative Approximations of Random Walk Transition Probabilities

  2011cites this paper
• From graphs to matrices, and back: new techniques for graph algorithms

  2011cites this paper
• Approximate distance oracles with improved preprocessing time

  2011cites this paper
• Sparse spanners vs. compact routing

  2011cites this paper
• On Approximate Distance Labels and Routing Schemes with Affine Stretch

  2011cites this paper
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions

  2011cites this paper
• Additive spanners and (α, β)-spanners

  2010cites this paper
• Algorithms and Models for Problems in Networking

  2010cites this paper
• Multipath Spanners

  2010cites this paper
• Sublinear Fully Distributed Partition with Applications

  2010cites this paper
• Distance Oracles beyond the Thorup-Zwick Bound

  2010cites this paper
• Approximate Shortest Path Queries Using Voronoi Duals

  2010cites this paper
• Collective Tree Spanners in Graphs with Bounded Parameters

  2010cites this paper
• Atlas: Approximating Shortest Paths in Social Graphs

  2010cites this paper
• A mean-variance model for the minimum cost flow problem with stochastic arc costs

  2010cites this paper
• Complexity analysis of tries and spanning tree problems

  2009cites this paper
• Average Size of Unstretched Remote-Spanners

  2009cites this paper
• Local Computation of Nearly Additive Spanners

  2009cites this paper
• Construction locale de sous-graphes couvrants peu denses

  2008cites this paper
• Distributed algorithms for ultrasparse spanners and linear size skeletons

  2008cites this paper
• Sparse Graph Spanners

  2008cites this paper
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation

  2008cites this paper
• On the locality of distributed sparse spanner construction

  2008cites this paper
• Schedulers for Optimistic Rate Based Flow Control

  2008cites this paper
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

  2007cites this paper
• Combinatorial algorithms for graphs and partially ordered sets

  2007cites this paper
• Low distortion spanners

  2007influential citation
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners

  2007cites this paper
• Spanners for bounded tree-length graphs

  2007cites this paper
• Spanners and emulators with sublinear distance errors

  2006cites this paper