Generating Sparse 2-Spanners

DOI10.1006/JAGM.1994.1032MaRDI QIDQ4312222zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, David Peleg

Publication date 22 November 1995

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1994.1032

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Generating sparse 2—spanners
• Generating Low-Degree 2-Spanners
• Approximating \(k\)-spanner problems for \(k>2\)
• scientific article; zbMATH DE number 1003288
• On the hardness of approximating spanners

Cited in

(35)

• Edge-disjoint spanners in tori
• Edge-disjoint spanners of complete graphs and complete digraphs
• NP-completeness of minimum spanner problems
• Sparse hypercube 3-spanners
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Graph spanners: a tutorial review
• Computing the \(k\) densest subgraphs of a graph
• Minimum \(t\)-spanners on subcubic graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Edge-disjoint spanners in Cartesian products of graphs
• Improved approximation for the directed spanner problem
• scientific article; zbMATH DE number 1003288 (Why is no real title available?)
• Models and algorithms for network reduction
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• Generating Low-Degree 2-Spanners
• Distributed spanner approximation
• Generating sparse 2—spanners
• Distance-Preserving Graph Contractions
• Approximating \(k\)-spanner problems for \(k>2\)
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• Covering a graph with densest subgraphs
• A study on modularity density maximization: column generation acceleration and computational complexity analysis
• Approximation of minimum weight spanners for sparse graphs
• Spanners in sparse graphs
• Complexity of the multiobjective minimum weight minimum stretch spanner problem
• Covering a graph with densest subgraphs
• Simple approximations for general spanner problems
• Approximation algorithm for extracting densest subgraph over matching-like constraints
• The complexity of landmark hub labeling
• Spanner approximations in practice
• Approximation algorithms for optimal hopsets
• Sparse hop spanners for unit disk graphs
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• Randomized priority algorithms

This page was built for publication: Generating Sparse 2-Spanners

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