Degree-constrained spanners for multidimensional grids

DOI10.1016/0166-218X(95)00050-2MaRDI QIDQ1917351zbMATH OpenFDO

Authors Arthur L. Liestman, Thomas C. Shermer, Christopher R. Stolte

Publication date 25 November 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(95)00050-2

zbMATH Keywords

distance functionsgraph spannergrids

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18)

Review text

A spanning subgraph \(S\) of a connected graph \(G\) is an \(f\)-spanner if for any pair of vertices \(u\) and \(v\) holds \(d_S(u, v)\leq f(d_G(u, v))\), where \(d_G\) and \(d_S\) denote distance functions in \(G\) and \(S\), respectively. The authors give \(f\)-spanners of maximum degree 3 and 4 for finite and infinite \(d\)-dimensional grids, where \(f(x)- x\) is a constant linear in \(d\).

Recommendations

• Grid spanners
• Spanners in graphs of bounded degree
• Additive graph spanners

Cites work

• Additive graph spanners
• An Optimal Synchronizer for the Hypercube
• Degree-Constrained Network Spanners with Nonconstant Delay
• Graph spanners
• Grid spanners
• scientific article; zbMATH DE number 4147467 (Why is no real title available?)

Cited in

(6)

• Edge-disjoint spanners in tori
• Edge-disjoint spanners of complete graphs and complete digraphs
• Edge-disjoint spanners in Cartesian products of graphs
• Lattice spanners of low degree
• Lattice spanners of low degree
• Grid spanners

This page was built for publication: Degree-constrained spanners for multidimensional grids

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