Portal de Periódicos da CAPES

Small congestion embedding of graphs into hypercubes

1999; Wiley; Volume: 33; Issue: 1 Linguagem: Inglês

10.1002/(sici)1097-0037(199901)33

1097-0037

Akira Matsubayashi, Shuichi Ueno,

Advanced Optical Network Technologies

NetworksVolume 33, Issue 1 p. 71-77 Small congestion embedding of graphs into hypercubes Akira Matsubayashi, Corresponding Author Akira Matsubayashi Department of Information Science, Utsunomiya University, Utsunomiya 321-8585, JapanDepartment of Information Science, Utsunomiya University, Utsunomiya 321-8585, JapanSearch for more papers by this authorShuichi Ueno, Shuichi Ueno Department of Physical Electronics, Tokyo Institute of Technology, Tokyo 152-8552, JapanSearch for more papers by this author Akira Matsubayashi, Corresponding Author Akira Matsubayashi Department of Information Science, Utsunomiya University, Utsunomiya 321-8585, JapanDepartment of Information Science, Utsunomiya University, Utsunomiya 321-8585, JapanSearch for more papers by this authorShuichi Ueno, Shuichi Ueno Department of Physical Electronics, Tokyo Institute of Technology, Tokyo 152-8552, JapanSearch for more papers by this author First published: 22 February 1999 https://doi.org/10.1002/(SICI)1097-0037(199901)33:1 3.0.CO;2-3Citations: 8AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract 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. © 1999 John Wiley & Sons, Inc. Networks 33: 71–77, 1999 Citing Literature Volume33, Issue1January 1999Pages 71-77 RelatedInformation