Generating sparse 2—spanners

DOI10.1007/3-540-55706-7_7MaRDI QIDQ5056130zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, David Peleg

Publication date 9 December 2022

Published in Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55706-7_7

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

Cites work

• An Optimal Synchronizer for the Hypercube
• Delaunay graphs are almost as good as complete graphs
• Fast network decomposition
• Generating sparse spanners for weighted graphs
• Graph spanners
• Grid spanners
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 4155926 (Why is no real title available?)
• Low-diameter graph decomposition is in NC
• Near-Linear Time Construction of Sparse Neighborhood Covers

Cited in

(6)

• Finding sparser directed spanners
• scientific article; zbMATH DE number 1003288 (Why is no real title available?)
• Generating Low-Degree 2-Spanners
• Generating Sparse 2-Spanners
• Greedily finding a dense subgraph
• On the hardness of approximating spanners

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 Q5056130)