Duckworth, W and Zito, M
(2000)
Sparse hypercube 3-spanners.
DISCRETE APPLIED MATHEMATICS, 103 (1-3).
pp. 289-295.
|
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: | 18 Jan 2023 19:41 |
| DOI: | 10.1016/S0166-218X(99)00246-2 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3166421 |
Dimensions
Dimensions
