Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
From MaRDI portal
Publication:4210144
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
Cited in
(only showing first 100 items - show all)- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Learning Arbitrary Statistical Mixtures of Discrete Distributions
- Tight bounds for learning a mixture of two Gaussians (extended abstract)
- Exponential Separation of Information and Communication for Boolean Functions
- Rectangles Are Nonnegative Juntas
- Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
- Approximating the Nash social welfare with indivisible items
- Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
- Approximating Shortest Paths in Graphs
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Improved approximation for the directed spanner problem
- The greedy spanner is existentially optimal
- 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)
- Light spanners for high dimensional norms via stochastic decompositions
- Clustered Integer 3SUM via Additive Combinatorics
- Inapproximability of combinatorial problems via small LPs and SDPs
- An interactive information odometer and applications
- Lower bounds on the size of semidefinite programming relaxations
- Faster algorithms for all-pairs small stretch distances in weighted graphs
- Bounds on the Spanner-Sum of Torus
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Sum-of-squares Lower Bounds for Planted Clique
- On the Lovász theta function for independent sets in sparse graphs
- All-Pairs Almost Shortest Paths
- Matching triangles and basing hardness on an extremely popular conjecture
- Efficiently learning Ising models on arbitrary graphs (extended abstract)
- On graph problems in a semi-streaming model
- Sparse quantum codes from quantum circuits
- Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
- Fast deterministic distributed algorithms for sparse spanners
- Spectral sparsification and regret minimization beyond matrix multiplicative updates
- Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
- Preserving statistical validity in adaptive data analysis (extended abstract)
- A polynomial-time bicriteria approximation scheme for planar bisection
- Random permutations using switching networks
- Randomized composable core-sets for distributed submodular maximization
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- The Power of Dynamic Distance Oracles
- Almost Optimal Pseudorandom Generators for Spherical Caps
- Dictionary learning and tensor decomposition via the sum-of-squares method
- Small value parallel repetition for general games
- \(\ell_p\) row sampling by Lewis weights
- A characterization of the capacity of online (causal) binary channels
- Time lower bounds for nonadaptive turnstile streaming algorithms
- Analysis of a classical matrix preconditioning algorithm
- 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
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- From independence to expansion and back again
- Multipath spanners
- Test-and-set in optimal space
- Dimensionality reduction for \(k\)-means clustering and low rank approximation
- Adjacency labeling schemes and induced-universal graphs
- Non-malleable reductions and applications
- 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
- Computing almost shortest paths (extended abstract)
- 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
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Reed-Muller codes for random erasures and errors
- On the complexity of Nash equilibria in anonymous games
- 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
- Quantum information complexity
- Transitive-closure spanners: a survey
- Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
- Secretary Problems with Non-Uniform Arrival Order
- Computing with Tangles
- A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
- The List Decoding Radius of Reed-Muller Codes over Small Fields
- The communication complexity of interleaved group products
- 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
- A fast algorithm for source-wise round-trip spanners
- Compact roundtrip routing with topology-independent node names
- Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
- scientific article; zbMATH DE number 7378699 (Why is no real title available?)
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- Sublinear fully distributed partition with applications
- FPTAS for \#BIS with degree bounds on one side
- Deterministic global minimum cut of a simple graph in near-linear time
- Leveled fully homomorphic signatures from standard lattices
- How well can graphs represent wireless interference?
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
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)
