Small congestion embedding of graphs into hypercubes

✍ Scribed by Matsubayashi, Akira; Ueno, Shuichi

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 103 KB
• Volume: 33
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199901)33:1<71::aid-net5>3.0.co;2-3

✦ Synopsis

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hypercube of dimension 6log N if the maximum degree of a vertex in G is no more than 6log N . Bhatt et al. showed that every N-vertex binary tree can be embedded in a hypercube of dimension log N with O(1) congestion. In this paper, we extend the results above and show the following: (1) Every N-vertex graph G can be embedded with unit congestion in a hypercube of dimension 2log N if the maximum degree of a vertex in G is no more than 2log N , and (2) every N-vertex binary tree can be embedded in a hypercube of dimension log N with congestion at most 5. The former answers a question posed by Kim and Lai. The latter is the first result that shows a simple embedding of a binary tree into an optimal-sized hypercube with an explicit small congestion of 5. This partially answers a question posed by Bhatt et al. The embeddings proposed here are quite simple and can be constructed in polynomial time.