Duckworth, W and Zito, M ORCID: 0009-0000-7182-3758
(2000)
Sparse hypercube 3-spanners.
DISCRETE APPLIED MATHEMATICS, 103 (1-3).
pp. 289-295.
ISSN 0166-218X
PDF
final.pdf - Author Accepted Manuscript Download (225kB) | Preview |
Abstract
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: | 07 Dec 2024 19:28 |
DOI: | 10.1016/S0166-218X(99)00246-2 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3166421 |