scientific article; zbMATH DE number 6696497

DOI10.4230/LIPICS.APPROX-RANDOM.2014.80MaRDI QIDQ2969610zbMATH OpenFDO

Authors Eden Chlamtac, Michael Dinitz

Publication date 22 March 2017

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2014.80

zbMATH Keywords

approximation algorithmsgraph spannershardness of approximation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Lowest-degree k-spanner: approximation and hardness
• Approximating \(k\)-spanner problems for \(k>2\)
• scientific article; zbMATH DE number 1757950
• Approximation of the degree-constrained minimum spanning hierarchies
• scientific article; zbMATH DE number 1305417
• scientific article; zbMATH DE number 1670859
• Approximating the smallest k-edge connected spanning subgraph by LP-rounding
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximating the smallest 2-vertex-connected spanning subgraph via low-high orders
• scientific article; zbMATH DE number 1182768

Cited in

(13)

• scientific article; zbMATH DE number 1670859 (Why is no real title available?)
• Lowest-degree k-spanner: approximation and hardness
• Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner
• Improved approximation for the directed spanner problem
• scientific article; zbMATH DE number 1003288 (Why is no real title available?)
• Generating Low-Degree 2-Spanners
• scientific article; zbMATH DE number 1757950 (Why is no real title available?)
• Approximating low-stretch spanners
• Approximating approximate distance oracles
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Distributed spanner approximation
• The norms of graph spanners
• Approximating the norms of graph spanners

This page was built for publication:

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