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

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, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Communication-efficient distributed graph clustering and sparsification under duplication models, Improved weighted additive spanners, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, Multi-priority graph sparsification, Capacity-preserving subgraphs of directed flow networks, Online Spanners in Metric Spaces, Unnamed Item, Small hop-diameter sparse spanners for doubling metrics, Tree spanners in planar graphs, Distributed construction of purely additive spanners, Computing with Tangles, Vertex fault-tolerant spanners for weighted points in polygonal domains, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Distributed distance-\(r\) covering problems on sparse high-girth graphs, Distributed algorithms for ultrasparse spanners and linear size skeletons, Approximate distance oracles with improved stretch for sparse graphs, Sparse hop spanners for unit disk graphs, Graph coarsening: from scientific computing to machine learning, Euclidean spanner graphs with degree four, Constructing sparse spanners for most graphs in higher dimensions, Consistency thresholds for the planted bisection model, On resilient graph spanners, Graph spanners in the streaming model: An experimental study, Thorup-Zwick emulators are universally optimal hopsets, Local routing in sparse and lightweight geometric graphs, Small stretch \((\alpha ,\beta )\)-spanners in the streaming model, Source-wise round-trip spanners, The geometry of graphs and some of its algorithmic applications, Well-partitioned chordal graphs, Spanners for bounded tree-length graphs, Balancing minimum spanning trees and shortest-path trees, Minimum \(t\)-spanners on subcubic graphs, Restrictions of minimum spanner problems, Covering metric spaces by few trees, Terminal embeddings, A PTAS for the sparsest 2-spanner of 4-connected planar triangulations, Near isometric terminal embeddings for doubling metrics, Approximate Distance Oracles with Improved Bounds, The Power of Dynamic Distance Oracles, Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture, Clustered Integer 3SUM via Additive Combinatorics, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false), Proof of the Satisfiability Conjecture for Large k, On the Complexity of Random Satisfiability Problems with Planted Solutions, Sum-of-squares Lower Bounds for Planted Clique, Sum of Squares Lower Bounds from Pairwise Independence, Inapproximability of Combinatorial Problems via Small LPs and SDPs, Preserving Statistical Validity in Adaptive Data Analysis, Local, Private, Efficient Protocols for Succinct Histograms, Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions, Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method, Randomized Composable Core-sets for Distributed Submodular Maximization, Dimensionality Reduction for k-Means Clustering and Low Rank Approximation, Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams, L _p Row Sampling by Lewis Weights, On the Lovász Theta function for Independent Sets in Sparse Graphs, The Complexity of the Simplex Method, An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm, Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs, Nearly-Linear Time Positive LP Solver with Faster Convergence Rate, Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates, Almost Optimal Pseudorandom Generators for Spherical Caps, Deterministic improved round-trip spanners, Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms, Self-stabilizing spanner topology control solutions in wireless ad hoc networks, On path-greedy geometric spanners, Continuous Yao graphs, New pairwise spanners, Approximation of minimum weight spanners for sparse graphs, The MST of symmetric disk graphs is light, New approximation algorithms for minimum cycle bases of graphs, Three problems on well-partitioned chordal graphs, Near-linear-time deterministic plane Steiner spanners for well-spaced point sets, Faster cut sparsification of weighted graphs, On dynamic shortest paths problems, On certain geometric properties of the Yao-Yao graphs, Spanners for geodesic graphs and visibility graphs, Computing the greedy spanner in near-quadratic time, Sublinear fully distributed partition with applications, Cycle bases in graphs characterization, algorithms, complexity, and applications, Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes, On the VC-dimension of unique round-trip shortest path systems, Quantum spectrum testing, Hardness and efficiency on \(t\)-admissibility for graph operations, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Streaming algorithm for graph spanners-single pass and constant processing time per edge, Max-stretch reduction for tree spanners, The \(\varTheta_5\)-graph is a spanner, Edge-disjoint spanners in Cartesian products of graphs, Approximate shortest paths guided by a small index, Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies, Graph spanners: a tutorial review, Lattice Spanners of Low Degree, A fast algorithm for source-wise round-trip spanners, Fault-tolerant approximate shortest-path trees, Light orthogonal networks with constant geometric dilation, Sparsification lower bound for linear spanners in directed graphs, Lattice spanners of low degree, Edge-disjoint spanners in tori, Multiple-edge-fault-tolerant approximate shortest-path trees, Constructing light spanners deterministically in near-linear time, On the approximability and hardness of the minimum connected dominating set with routing cost constraint, Mixed-integer programming approaches for the tree \(t^*\)-spanner problem, Multi-colored spanning graphs, Geometric spanner games, Light spanners for high dimensional norms via stochastic decompositions, Edge-disjoint spanners of complete graphs and complete digraphs, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Additive sparse spanners for graphs with bounded length of largest induced cycle, Fault tolerant additive and \((\mu, \alpha)\)-spanners, NP-completeness of minimum spanner problems, Approximating Euclidean distances by small degree graphs, Neighborhood hypergraph model for topological data analysis, Lasserre integrality gaps for graph spanners and related problems

Cites Work