| 直径不超过4的树的割宽 |
| |
| 引用本文： | 林诒勋.直径不超过4的树的割宽[J].高校应用数学学报(英文版),2003,18(3):361-369. |
| |
| 作者姓名： | 林诒勋 |
| |
| 作者单位： | Lin YixunDept.of Math.，Zhengzhou Univ.，Zhengzhou 450052，China. |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China( 1 0 0 71 0 76) |
| |
| 摘 要： | § 1 IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see 2 ] ) .We shall follow the graph-theoretic terminology and notation of 1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…
|
| 收稿时间： | 17 April 2002 |
The cutwidth of trees with diameter at most 4 |
| |
| Lin?Yixun.The cutwidth of trees with diameter at most 4[J].Applied Mathematics A Journal of Chinese Universities,2003,18(3):361-369. |
| |
| Authors: | Lin Yixun |
| |
| Institution: | (1) Dept. of Math., Zhengzhou Univ., 450052 Zhengzhou, China |
| |
| Abstract: | The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well. |
| |
| Keywords: | graph labeling cutwidth bandwidth trees with diameter 4 |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
