On sparse spanners of weighted graphs
From MaRDI portal
Publication:1196368
Recommendations
Cites work
- A note on the tree realizability of a distance matrix
- An Optimal Synchronizer for the Hypercube
- Complexity of network synchronization
- Delaunay graphs are almost as good as complete graphs
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Graph spanners
- scientific article; zbMATH DE number 4155925 (Why is no real title available?)
- scientific article; zbMATH DE number 4155926 (Why is no real title available?)
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 4070353 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 192896 (Why is no real title available?)
- scientific article; zbMATH DE number 4119974 (Why is no real title available?)
- scientific article; zbMATH DE number 3189017 (Why is no real title available?)
- On optimal realizations of finite metric spaces by graphs
- Partitions ofN-Space by Hyperplanes
- Ramanujan graphs
- Reconstructing the shape of a tree from observed dissimilarity data
- Regular d-valent graphs of girth 6 and 2(d2−d+1) vertices
- Routing with Polynomial Communication-Space Trade-Off
- Shortest paths in Euclidean graphs
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
Cited in
(only showing first 100 items - show all)- Light orthogonal networks with constant geometric dilation
- Edge-disjoint spanners in tori
- Edge-disjoint spanners of complete graphs and complete digraphs
- NP-completeness of minimum spanner problems
- Approximating Euclidean distances by small degree graphs
- Euclidean spanner graphs with degree four
- Constructing sparse spanners for most graphs in higher dimensions
- Restrictions of minimum spanner problems
- Thorup-Zwick emulators are universally optimal hopsets
- Continuous Yao graphs
- New pairwise spanners
- Spanners for geodesic graphs and visibility graphs
- On the VC-dimension of unique round-trip shortest path systems
- Fault-tolerant approximate shortest-path trees
- The geometry of graphs and some of its algorithmic applications
- Balancing minimum spanning trees and shortest-path trees
- Computing the greedy spanner in near-quadratic time
- Sublinear fully distributed partition with applications
- Graph spanners: a tutorial review
- A fast algorithm for source-wise round-trip spanners
- Sparsification lower bound for linear spanners in directed graphs
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Constructing light spanners deterministically in near-linear time
- Light spanners for high dimensional norms via stochastic decompositions
- Neighborhood hypergraph model for topological data analysis
- Lasserre integrality gaps for graph spanners and related problems
- Graph coarsening: from scientific computing to machine learning
- Local routing in sparse and lightweight geometric graphs
- Well-partitioned chordal graphs
- Minimum \(t\)-spanners on subcubic graphs
- Covering metric spaces by few trees
- Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes
- Hardness and efficiency on \(t\)-admissibility for graph operations
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- The \(\varTheta_5\)-graph is a spanner
- Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
- Geometric spanner games
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Spanners for bounded tree-length graphs
- Terminal embeddings
- Deterministic improved round-trip spanners
- On certain geometric properties of the Yao-Yao graphs
- Max-stretch reduction for tree spanners
- Edge-disjoint spanners in Cartesian products of graphs
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Source-wise round-trip spanners
- Near isometric terminal embeddings for doubling metrics
- Self-stabilizing spanner topology control solutions in wireless ad hoc networks
- On path-greedy geometric spanners
- Three problems on well-partitioned chordal graphs
- Faster cut sparsification of weighted graphs
- Lattice spanners of low degree
- Lattice spanners of low degree
- Lower bound for sparse Euclidean spanners
- Low distortion spanners
- 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 (extended abstract)
- Sum-of-squares Lower Bounds for Planted Clique
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Inapproximability of combinatorial problems via small LPs and SDPs
- Preserving statistical validity in adaptive data analysis (extended abstract)
- 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
- _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
- Polynomially low error PCPs with \(\operatorname{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: a problem that optimally separates quantum from classical computing
- 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 Carathéodory'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
This page was built for publication: On sparse spanners of weighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196368)
