Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

DOI10.1137/S0097539794261295zbMATH Open0915.68077OpenAlexW2097747425MaRDI QIDQ4210144FDOQ4210144

Edith Cohen

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794261295

Recommendations

• Fast constructions of light-weight spanners for general graphs
• Fast constructions of lightweight spanners for general graphs
• A fast algorithm for source-wise round-trip spanners
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Approximation algorithms for quickest spanning tree problems
• Algorithms – ESA 2004
• Computing the Greedy Spanner in Near-Quadratic Time
• Computing the greedy spanner in near-quadratic time
• scientific article; zbMATH DE number 7768369

zbMATH Keywords

shortest pathsparallel algorithmsgraph spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Cited In (only showing first 100 items - show all)

• On graph problems in a semi-streaming model
• Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
• Approximating the Nash Social Welfare with Indivisible Items
• Proof of the Satisfiability Conjecture for Large k
• Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
• Fast deterministic distributed algorithms for sparse spanners
• Improved Approximation for the Directed Spanner Problem
• The Power of Dynamic Distance Oracles
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Sum of Squares Lower Bounds from Pairwise Independence
• Multipath spanners
• An Interactive Information Odometer and Applications
• Inapproximability of Combinatorial Problems via Small LPs and SDPs
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Deterministic improved round-trip spanners
• Efficiently Learning Ising Models on Arbitrary Graphs
• All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
• Source-wise round-trip spanners
• Beyond the Euler Characteristic
• Transitive-closure spanners: a survey
• Preserving Statistical Validity in Adaptive Data Analysis
• Random Permutations using Switching Networks
• Computing with Tangles
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• Secretary Problems with Non-Uniform Arrival Order
• Small Value Parallel Repetition for General Games
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Inapproximability of Nash Equilibrium
• Minimizing Flow-Time on Unrelated Machines
• Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
• Sketching and Embedding are Equivalent for Norms
• Ramsey partitions and proximity data structures
• Approximate distance oracles for graphs with dense clusters
• From Independence to Expansion and Back Again
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Adjacency Labeling Schemes and Induced-Universal Graphs
• Non-malleable Reductions and Applications
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Learning Mixtures of Gaussians in High Dimensions
• Approximate k -flat Nearest Neighbor Search
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Randomized Rounding for the Largest Simplex Problem
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Approximate Distance Oracles with Improved Bounds
• The Directed Grid Theorem
• Sublinear fully distributed partition with applications
• Testing Cluster Structure of Graphs
• Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Succinct Randomized Encodings and their Applications
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• New Doubling Spanners: Better and Simpler
• Shortest-path queries in static networks
• On the Complexity of Nash Equilibria in Anonymous Games
• Garbled RAM From One-Way Functions
• High Parallel Complexity Graphs and Memory-Hard Functions
• Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
• Succinct Garbling and Indistinguishability Obfuscation for RAM Programs
• Computing graph spanners in small memory: fault-tolerance and streaming
• Quantum Information Complexity
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions
• 2-Server PIR with Sub-Polynomial Communication
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Multiplicative Approximations of Random Walk Transition Probabilities
• On dynamic shortest paths problems
• All-pairs small-stretch paths
• Forrelation
• Learning Arbitrary Statistical Mixtures of Discrete Distributions
• Exponential Separation of Information and Communication for Boolean Functions
• Rectangles Are Nonnegative Juntas
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Approximating Shortest Paths in Graphs
• How Well Can Graphs Represent Wireless Interference?
• Leveled Fully Homomorphic Signatures from Standard Lattices
• Online Submodular Welfare Maximization
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
• The Complexity of the Simplex Method
• Greedy Algorithms for Steiner Forest
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Clustered Integer 3SUM via Additive Combinatorics
• Bypassing KLS
• Faster Canonical Forms for Primitive Coherent Configurations
• On the Lovász Theta function for Independent Sets in Sparse Graphs
• Consistency thresholds for the planted bisection model
• Solving the Shortest Vector Problem in 2 ⁿ Time Using Discrete Gaussian Sampling
• Excluded Grid Theorem
• All-Pairs Almost Shortest Paths
• Sum-of-squares Lower Bounds for Planted Clique
• Tight Bounds for Learning a Mixture of Two Gaussians
• Prioritized Metric Structures and Embedding
• Almost Optimal Pseudorandom Generators for Spherical Caps
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Sparse Quantum Codes from Quantum Circuits
• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
• A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
• Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

This page was built for publication: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210144)