Sparse hypercube 3-spanners (Q1570842): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Generating Sparse 2-Spanners / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph spanners / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Optimal Synchronizer for the Hypercube / rank | |||
Normal rank |
Revision as of 10:58, 30 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sparse hypercube 3-spanners |
scientific article |
Statements
Sparse hypercube 3-spanners (English)
0 references
11 July 2000
0 references
A hypercube \(H_d\) is a graph whose vertex set is the set of all Boolean vectors of dimension \(d\) and in which two vertices are adjacent if and only if their Hamming distance is 1. A \(t\)-spanner of a graph \(G\) is a spanning subgraph \(S(G)\) of \(G\) such that any two vertices \(u\), \(v\) which are adjacent in \(G\) have distance at most \(t\) in \(S(G)\). The paper studies minimal numbers of edges of 3-spanners of hypercubes.
0 references
spanner
0 references
dominating set
0 references
hypercube
0 references