Dense edge-disjoint embedding of complete binary trees in interconnection networks (Q1583538)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Dense edge-disjoint embedding of complete binary trees in interconnection networks
scientific article

    Statements

    Dense edge-disjoint embedding of complete binary trees in interconnection networks (English)
    0 references
    0 references
    26 October 2000
    0 references
    We describe dense edge-disjoint embeddings of the complete binary tree with \(n\) leaves in the following \(n\)-node communication networks: the hypercube, the de Bruijn and shuffle-exchange networks and the two-dimensional mesh. For the mesh and the shuffle-exchange graphs each edge is regarded as two parallel (or anti-parallel) edges. The embeddings have the following properties: paths of the tree are mapped onto edge-disjoint paths of the host graph and at most two tree nodes (just one of which is a leaf) are mapped onto each host node. We prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except in the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. The embeddings facilitate efficient implementation of many P-RAM algorithms on these networks.
    0 references
    parallel algorithms
    0 references
    graph embedding
    0 references
    binary tree
    0 references
    hypercube
    0 references
    mesh
    0 references
    De Bruijn network
    0 references
    shuffle-exchange network
    0 references

    Identifiers