摘要
起源于超大规模集成电路设计和网络通讯的图的割宽(cutwidth)问题,就是把一个含有n个顶点的图G的全部顶点分别安装在一条直线的不同的整数点上,使得跨越各顶点的边数的最大值(即稠密度)达到最小.文章得到了k–割宽临界树的一些构造方法(k≥3).
Originating from VLSI design and network communication, the cutwidth problem is to embed all the apexes of graph G with n apexes onto the different integral points of a straight line, making the maximum number of overlap edges minimized. This paper gets some methods of constructing κ-cutwidth critical trees（κ≥3）.
出处
《天中学刊》
2008年第2期6-10,共5页
Journal of Tianzhong
基金
河南省自然科学基金项目(082300410040)
关键词
割宽
树
临界树
cutwidth
trees
critical trees
