pase@ogcvax.UUCP (10/27/87)
What does it mean to show a graph G is a subgraph of a hypercube? I see two possibilities: 1) Both nodes and edges of G must map one-to-one such that the connectedness remains the same. 2) Groups of connected nodes in G may be mapped to a single node of a hypercube such that the new graph G' which results is a hypercube. The problem of hypercube embedding is NP-complete, I'm just trying to figure out exactly what embedding means. If I had to guess, I would say #1. Would someone who knows please respond? -- Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@cse.ogc.edu.csnet
rabaeza@hubcap.UUCP (10/30/87)
In article <599@hubcap.UUCP> ogcvax!pase@uunet.uu.net (Douglas M. Pase) writes: >What does it mean to show a graph G is a subgraph of a hypercube? >I see two possibilities: > > 1) Both nodes and edges of G must map one-to-one such that > the connectedness remains the same. > > 2) Groups of connected nodes in G may be mapped to a single > node of a hypercube such that the new graph G' which results > is a hypercube. > >The problem of hypercube embedding is NP-complete, I'm just trying to figure >out exactly what embedding means. If I had to guess, I would say #1. Would >someone who knows please respond? >-- >Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@cse.ogc.edu.csnet An embedding is a one-to-one mapping. For example a n-level complete binary tree is embeddable in a hypercube of size 2^(n+2) and is not embeddable in one of size 2^(n+1). More general embeddings of a graph in the hypercube (or other graph) are characterized by 3 parameters: expansion (number of nodes of the hypercube over the number of vertices in the graph), dilation (maximum stretching of an edge of the graph in the hypercube -for example the one-to-one embedding has dilation 1), and load factor (maximum number of edged mapped to a single edge of the hypercube). For example, is possible to embed a n-level complete binary tree in a hypercube of size 2^(n+1) (expansion is 2) with dilation 2. Ricardo -- rabaeza@waterloo.csnet 1-519-885-1211 x6709 Ricardo Baeza-Yates rabaeza%waterloo@csnet-relay.arpa CS Dept., U. Waterloo {allegra,decvax,ihnp4,utzoo}!watmath!watmum!rabaeza Waterloo, Ont. N2L3G1