THE CUTWIDTH OF TREES WITH DIAMETER AT MOST 4 被引量：1

THE CUTWIDTH OF TREES WITH DIAMETER AT MOST 4

下载PDF

导出

摘要 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. 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.

作者 Lin YixunDept.of Math., Zhengzhou Univ., Zhengzhou 450052, China.

出处《Applied Mathematics(A Journal of Chinese Universities)》 SCIE CSCD 2003年第3期361-369,共9页 高校应用数学学报（英文版）（B辑）

基金 Supported by the National Natural Science Foundation of China( 1 0 0 71 0 76)

关键词 graph labeling cutwidth BANDWIDTH trees with diameter 4 graph labeling, cutwidth, bandwidth, trees with diameter 4

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献1

1Lin Yixun Li Xianglu Yang Aifeng.A DEGREE SEQUENCE METHOD FOR THE CUTWIDTH PROBLEM OF GRAPHS[J].Applied Mathematics(A Journal of Chinese Universities),2002,17(2):125-134. 被引量：2

二级参考文献8

1Chung, F.R.K., Labelings of graphs,In: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory,1988,3:151-168.
2Chinn, P.Z., Chvatalova, J., Dewdney, A.K., et al., The bandwidth problem forgraphs and matrices-a survey, J. Graph Theory, 1982,6:223-254.
3Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theoryof NP-completeness, Freeman and Sons, San Francisco, 1979.
4Yannakakis, M., A polynomial algorithm for the min-cut arrangement of trees, J.ACM, 1985,32(4):950-989.
5Chung,F.R.K., On the cutwidth and the topological bandwidth of a tree, SIAMJ.Alg.& Disc. Meth., 1985,6(2):268-277.
6Chung, M., Makedon, F., Sudborough, I.H., et al., Polynomial time algorithms forthe min cut problem on degree restricted trees, SIAM J. Comput., 1985,14:158-177.
7Liu Hongen and Yuan Jinjiang, Cutwidth problem on graphs, Appl. Math. J. ChineseUniv. Ser A., 1995,10(3):339-348.
8Lin Yixun, A level structure approach on the bandwidth problem for special graphs,Annals of the New York Academy of Sciences, 1989,576:344-357.

共引文献1

1方侃.毛毛虫树三角和四边形变换下的割宽不变性[J].福州大学学报（自然科学版）,2009,37(4):482-485.

引证文献1

1张振坤,余春华.k–割宽临界树的一些构造方法(k≥3)[J].天中学刊,2008,23(2):6-10.

1鄢仁政.超图的最优标号与特征值[J].数学研究,2013,46(4):424-427.
2赵永成,原晋江.关于图的拓扑带宽与割宽的关系的一些结果[J].河南科学,1996,14(3):237-240.
3张振坤,余春华.k–割宽临界树的一些构造方法(k≥3)[J].天中学刊,2008,23(2):6-10.
4方侃.毛毛虫树三角和四边形变换下的割宽不变性[J].福州大学学报（自然科学版）,2009,37(4):482-485.
5朱雅音,万丰,王化文.确定两个任意简单多边形空间关系的算法[J].计算机工程与应用,2003,39(1):91-93. 被引量：5
6刘鸿恩,原晋江.图的割宽问题[J].高校应用数学学报（A辑）,1995,10(3):339-348. 被引量：1
7林诒勋.割宽与图的有关参数(英文)[J].郑州大学学报（理学版）,2002,34(1):1-5.
8张纯,吴欧,毛磊,张燕.泰勒中值定理的教学研究[J].软件（教育现代化）（电子版）,2013,3(1):116-117.
9GAO Hongzhu (Department of Mathematics, Beijing Normal University, Beijing,China).NORMAL EULER NUMBERS OF EMBEDDING NONORIENTABLE SURFACES IN 4-MANIFOLDS[J].Systems Science and Mathematical Sciences,1996,9(3):242-251.
10M.I. Ostrovskii.MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS[J].Acta Mathematica Scientia,2011,31(2):634-640. 被引量：1

Applied Mathematics(A Journal of Chinese Universities)

2003年第3期

浏览历史

内容加载中请稍等...

THE CUTWIDTH OF TREES WITH DIAMETER AT MOST 4 被引量：1

参考文献1

二级参考文献8

共引文献1

引证文献1

相关作者

相关机构

相关主题

浏览历史