The carving-width of generalized hypercubes |
| |
| Authors: | Kyohei Kozawa Koichi Yamazaki |
| |
| Affiliation: | a Electric Power Development Co., Ltd. 6-15-1, Ginza, Chuo-ku, Tokyo, 104-8165, Japanb Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japanc Department of Computer Science, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma 376-8515, Japan |
| |
| Abstract: | The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes. |
| |
| Keywords: | Carving-width Hypercube Hamming graph Grid Torus |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
