Generating Low-Degree 2-Spanners

DOI10.1137/S0097539794268753MaRDI QIDQ4210117zbMATH OpenFDO

Authors Guy Kortsarz, David Peleg

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/S0097539794268753

zbMATH Keywords

approximationgraph spannersNP-hardnessrandomized rounding

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1003288
• Generating Sparse 2-Spanners
• Generating sparse 2—spanners
• On 2-connected spanning subgraphs with low maximum degree
• Lattice spanners of low degree
• Lattice spanners of low degree
• scientific article; zbMATH DE number 6696497
• Lowest-degree k-spanner: approximation and hardness
• Constructing plane spanners of bounded degree and low weight
• scientific article; zbMATH DE number 1947396

Cited in

(19)

• Edge-disjoint spanners in tori
• Edge-disjoint spanners of complete graphs and complete digraphs
• Graph spanners: a tutorial review
• Local heuristics and the emergence of spanning subgraphs in complex networks
• Edge-disjoint spanners in Cartesian products of graphs
• Lowest-degree k-spanner: approximation and hardness
• scientific article; zbMATH DE number 1003288 (Why is no real title available?)
• Spanners in graphs of bounded degree
• Generating Sparse 2-Spanners
• Distributed spanner approximation
• Generating sparse 2—spanners
• The norms of graph spanners
• Approximating \(k\)-spanner problems for \(k>2\)
• Approximating the norms of graph spanners
• On the hardness of approximating spanners
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• Approximation algorithms for optimal hopsets
• Bounded degree spanners of the hypercube
• Sparse hop spanners for unit disk graphs

This page was built for publication: Generating Low-Degree 2-Spanners

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