Loading...
Please wait, while we are loading the content...
Similar Documents
On hypercube 3-spanners.
| Content Provider | CiteSeerX |
|---|---|
| Author | Gregor, Petr |
| Abstract | Abstract. A spanning subgraph S of a graph G is t-spanner if every two neighbors in G have distance at most t in S. We show that every 3-spanner of the n-dimensional hypercube Qn has at least (2 − o(1))2n edges. On the other hand, there is a 3-spanner of Qn with at most 3.5 · 2n edges. This improves previously known lower and upper bounds on the minimal size of hypercube 3-spanners. Furthermore, we present two constructions that are efficient for small dimensions. 1. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Hypercube 3-spanners N-dimensional Hypercube Qn Minimal Size Small Dimension Upper Bound |
| Content Type | Text |
| Resource Type | Article |
