2022-08-18T23:06:54Zhttps://kanazawa-u.repo.nii.ac.jp/?action=repository_oaipmhoai:kanazawa-u.repo.nii.ac.jp:000076282022-05-11T01:20:11Z00934:00935:00936
Small congestion embedding of graphs into hypercubesenghttp://hdl.handle.net/2297/3642Journal ArticleMatsubayashi, AkiraUeno, Shuichi金沢大学大学院自然科学研究科知能情報・数理金沢大学工学部Networks33171771999-01-150028-3045John Wiley & SonsWe 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. © 1999 John Wiley & Sons, Inc. Networks 33: 71-77, 1999.authorhttps://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=7628&item_no=1&attribute_id=26&file_no=12017-10-03