Premium
The steiner problem in the hypercube
Author(s) -
Miller Zevi,
Perkel Manley
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220102
Subject(s) - hypercube , combinatorics , mathematics , upper and lower bounds , steiner tree problem , discrete mathematics , set (abstract data type) , computer science , mathematical analysis , programming language
Let Q ( n ) be the n ‐dimensional hypercube, and X , a set of points in Q ( n ). The Steiner problem for the hypercube is to find the smallest possible number L ( n,X ) of edges in any subtree of Q ( n ) that spans X . We obtain the following results: 1 An exact formula for L ( n,X ), when | X | ≤ 5. 2 The bound L ( n,X ) ≤ ( n k +1 ) + (2 + o (1)) ([log ( k )]/ k )( n k ) as k → ∞, when X is the set of all points in Q ( n ) of a given weight k + 1, provided ( k 2 /[log ( k )]) 1 + 1/ k ≤ n . 3 NP‐completeness of deciding L ( n,X ) even when every point of X has weight at most 2.