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

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

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

(33)

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

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)