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

DOI10.1137/S0097539794261295zbMATH Open0915.68077OpenAlexW2097747425MaRDI QIDQ4210144FDOQ4210144

Authors: 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 the Lovász theta function for independent sets in sparse graphs
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• On graph problems in a semi-streaming model
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Fast deterministic distributed algorithms for sparse spanners
• Random permutations using switching networks
• The Power of Dynamic Distance Oracles
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Small value parallel repetition for general games
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Nearly-linear time positive LP solver with faster convergence rate
• Inapproximability of Nash equilibrium
• Sketching and embedding are equivalent for norms
• Minimizing flow-time on unrelated machines
• Multipath spanners
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• From independence to expansion and back again
• Dimensionality reduction for \(k\)-means clustering and low rank approximation
• Adjacency labeling schemes and induced-universal graphs
• Non-malleable reductions and applications
• Computing almost shortest paths (extended abstract)
• 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
• Approximate distance oracles with improved bounds
• The directed grid theorem
• Testing cluster structure of graphs
• Deterministic improved round-trip spanners
• Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity
• Succinct randomized encodings and their applications
• On the complexity of Nash equilibria in anonymous games
• All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
• Indistinguishability obfuscation for Turing machines with unbounded memory
• Succinct garbling and indistinguishability obfuscation for RAM programs
• Garbled RAM from one-way functions
• Source-wise round-trip spanners
• Transitive-closure spanners: a survey
• Quantum information complexity
• Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
• 2-server PIR with sub-polynomial communication
• Computing with Tangles
• Secretary Problems with Non-Uniform Arrival Order
• Ramsey partitions and proximity data structures
• Approximate distance oracles for graphs with dense clusters
• Forrelation: a problem that optimally separates quantum from classical computing
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Sublinear fully distributed partition with applications
• Leveled fully homomorphic signatures from standard lattices
• How well can graphs represent wireless interference?
• The complexity of the simplex method
• Super-resolution, extremal functions and the condition number of Vandermonde matrices
• Online submodular welfare maximization: greedy beats 1/2 in random order
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• New Doubling Spanners: Better and Simpler
• Shortest-path queries in static networks
• High Parallel Complexity Graphs and Memory-Hard Functions
• Computing graph spanners in small memory: fault-tolerance and streaming
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Greedy algorithms for Steiner forest
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• Faster canonical forms for primitive coherent configurations (extended abstract)
• On dynamic shortest paths problems
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• All-pairs small-stretch paths
• Excluded grid theorem: improved and simplified
• 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 Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximating the Nash social welfare with indivisible items
• Approximating Shortest Paths in Graphs
• Improved approximation for the directed spanner problem
• Proof of the satisfiability conjecture for large \(k\)
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Clustered Integer 3SUM via Additive Combinatorics
• Consistency thresholds for the planted bisection model
• Inapproximability of combinatorial problems via small LPs and SDPs
• An interactive information odometer and applications
• Lower bounds on the size of semidefinite programming relaxations
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• All-Pairs Almost Shortest Paths
• Sum-of-squares Lower Bounds for Planted Clique
• 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
• Randomized composable core-sets for distributed submodular maximization
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Almost Optimal Pseudorandom Generators for Spherical Caps
• \(\ell_p\) row sampling by Lewis weights

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)