Degree-constrained spanners for multidimensional grids (Q1917351)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Degree-constrained spanners for multidimensional grids |
scientific article; zbMATH DE number 897437
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Degree-constrained spanners for multidimensional grids |
scientific article; zbMATH DE number 897437 |
Statements
Degree-constrained spanners for multidimensional grids (English)
0 references
25 November 1996
0 references
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\).
0 references
graph spanner
0 references
distance functions
0 references
grids
0 references
