Sparse hypercube 3-spanners

Duckworth, W and Zito, M
(2000) Sparse hypercube 3-spanners. DISCRETE APPLIED MATHEMATICS, 103 (1-3). pp. 289-295.

[img] PDF
final.pdf - Author Accepted Manuscript

Download (225kB) | Preview


A t-spanner of a graph G=(V,E), is a sub-graph SG=(V,E′), such that E′⊆E and for every edge {u,v}∈E, there is a path from u to v in SG of length at most t. A minimum-edge t-spanner of a graph G, SG′, is the t-spanner of G with the fewest edges. For general graphs and for t=2, the problem of determining for a given integer s, whether |E(SG′)|≤s is NP-Complete (Peleg and Schaffer, J. Graph Theory 13(1) (1989) 99-116). Peleg and Ullman (SIAM J. Comput. 18(4) (1989) 740-747), give a method for constructing a 3-spanner of the n-vertex Hypercube with fewer than 7n edges. In this paper we give an improved construction giving a 3-spanner of the n-vertex Hypercube with fewer than 4n edges and we present a lower bound of 3n/2-o(1) on the size of the optimal Hypercube 3-spanner. © 2000 Elsevier Science B.V.

Item Type: Article
Uncontrolled Keywords: hypercube, spanner, Cartesian product, dominating set
Depositing User: Symplectic Admin
Date Deposited: 28 Nov 2022 09:33
Last Modified: 18 Jan 2023 19:41
DOI: 10.1016/S0166-218X(99)00246-2
Related URLs: