On sparse spanners of weighted graphs

DOI10.1007/BF02189308zbMath0762.05039OpenAlexW2002041206MaRDI QIDQ1196368

Publication date: 14 December 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131235

zbMATH Keywords

algorithm distance planar graphs weighted graphs Euclidean graphs sparse spanners

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (only showing first 100 items - show all)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ Light graphs with small routing cost ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ Truly Optimal Euclidean Spanners ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Optimal (Euclidean) Metric Compression ⋮ Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition ⋮ The List Decoding Radius of Reed-Muller Codes over Small Fields ⋮ A Characterization of the Capacity of Online (causal) Binary Channels ⋮ Reed-Muller Codes for Random Erasures and Errors ⋮ Forrelation ⋮ Quantum Information Complexity ⋮ Sparse Quantum Codes from Quantum Circuits ⋮ Small Value Parallel Repetition for General Games ⋮ An Interactive Information Odometer and Applications ⋮ The communication complexity of interleaved group products ⋮ Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem ⋮ Approximating the Nash Social Welfare with Indivisible Items ⋮ On the Complexity of Nash Equilibria in Anonymous Games ⋮ Hardness of Graph Pricing Through Generalized Max-Dicut ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension ⋮ Inapproximability of Nash Equilibrium ⋮ Indistinguishability Obfuscation for Turing Machines with Unbounded Memory ⋮ Succinct Garbling and Indistinguishability Obfuscation for RAM Programs ⋮ Succinct Randomized Encodings and their Applications ⋮ Garbled RAM From One-Way Functions ⋮ Non-malleable Reductions and Applications ⋮ Leveled Fully Homomorphic Signatures from Standard Lattices ⋮ Sketching and Embedding are Equivalent for Norms ⋮ Prioritized Metric Structures and Embedding ⋮ A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds ⋮ Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries ⋮ Bypassing KLS ⋮ FPTAS for #BIS with Degree Bounds on One Side ⋮ Lower Bounds on the Size of Semidefinite Programming Relaxations ⋮ 2-Server PIR with Sub-Polynomial Communication ⋮ Fast Matrix Multiplication ⋮ High Parallel Complexity Graphs and Memory-Hard Functions ⋮ Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity ⋮ Test-and-Set in Optimal Space ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ How Well Can Graphs Represent Wireless Interference? ⋮ Excluded Grid Theorem ⋮ The Directed Grid Theorem ⋮ Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time ⋮ Beyond the Euler Characteristic ⋮ Faster Canonical Forms for Primitive Coherent Configurations ⋮ Random Permutations using Switching Networks ⋮ Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms ⋮ Testing Cluster Structure of Graphs ⋮ Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling ⋮ Learning Arbitrary Statistical Mixtures of Discrete Distributions ⋮ Tight Bounds for Learning a Mixture of Two Gaussians ⋮ Learning Mixtures of Gaussians in High Dimensions ⋮ Efficiently Learning Ising Models on Arbitrary Graphs ⋮ Approximate k -flat Nearest Neighbor Search ⋮ Optimal Data-Dependent Hashing for Approximate Near Neighbors ⋮ Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms ⋮ From Independence to Expansion and Back Again ⋮ Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices ⋮ Analysis of a Classical Matrix Preconditioning Algorithm ⋮ A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection ⋮ Minimizing Flow-Time on Unrelated Machines ⋮ Randomized Rounding for the Largest Simplex Problem ⋮ Greedy Algorithms for Steiner Forest ⋮ Secretary Problems with Non-Uniform Arrival Order ⋮ Online Submodular Welfare Maximization ⋮ Unnamed Item ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics ⋮ Light Euclidean Spanners with Steiner Points ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Transitive-Closure Spanners: A Survey ⋮ Geodesic Spanners for Points on a Polyhedral Terrain ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Unnamed Item ⋮ Network flow spanners ⋮ Approximating Shortest Paths in Graphs ⋮ The Minimal Manhattan Network Problem in Three Dimensions ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Rectangles Are Nonnegative Juntas ⋮ Spanners of Complete k-Partite Geometric Graphs ⋮ Exponential Separation of Information and Communication for Boolean Functions ⋮ The Greedy Spanner Is Existentially Optimal ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension ⋮ Distance-Preserving Graph Contractions ⋮ Light Spanners ⋮ Distance-Preserving Graph Contractions ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Metric Spaces with Expensive Distances ⋮ Unnamed Item

Cites Work

This page was built for publication: On sparse spanners of weighted graphs