Bounded degree spanners of the hypercube

DOI10.37236/9074zbMath1444.05103arXiv1910.09868OpenAlexW3042057333MaRDI QIDQ782941

Adam Zsolt Wagner, Mehtab Sawhney, Rajko Nenadov, Benjamin Sudakov

Publication date: 29 July 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.09868

zbMATH Keywords

\(k\)-additive spannersbounded degree subgraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• On plane geometric spanners: a survey and open problems
• On 2-detour subgraphs of the hypercube
• A survey of integrity
• Two results about the hypercube
• Vertex fault tolerant additive spanners
• Graph spanners: a tutorial review
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Additive spanners and (α, β)-spanners
• Onk-detour subgraphs of hypercubes
• Generating Low-Degree 2-Spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• The 4/3 Additive Spanner Exponent Is Tight
• Hypercube subgraphs with minimal detours
• Additive graph spanners
• New Additive Spanners

This page was built for publication: Bounded degree spanners of the hypercube