期刊文献+
共找到2篇文章
< 1 >
每页显示 20 50 100
SOME COMBINATORIAL OPTIMIZATION PROBLEMS ARISING FROM VLSI CIRCUIT DESIGN 被引量:2
1
作者 刘彦佩 《Applied Mathematics(A Journal of Chinese Universities)》 SCIE CSCD 1993年第2期218-235,共18页
This paper is basically a survey to show a number of combinatorial optimization problems arising from VLSI circuit design. Some of them including the existence problem, minimax problem, net representation, bend minimi... This paper is basically a survey to show a number of combinatorial optimization problems arising from VLSI circuit design. Some of them including the existence problem, minimax problem, net representation, bend minimization, area minimization, placement problem, routing problem, etc. are especially discussed with new results and theoretical ideas for treating them. Finally, a number of problems for further research are mentioned. 展开更多
关键词 VLSI Circuit Design rectilinear embedding rectilinear Convexity Forbidden Configuration Combinatorial Optimization.
下载PDF
GENERAL THEORETICAL RESULTS ON RECTILINEAR EMBEDABILITY OF GRAPHS
2
作者 刘彦佩 A.MORGANA B.SIMEONE 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 1991年第2期187-192,共6页
In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and ... In the design of certain kinds of electronic circuits the following question arises:given a non-negative integer k, what graphs admit of a plane embedding such that every edge is a broken lineformed by horizontal and vertical segments and having at mort k bends? Any such graph is said tobe k--rectilinear. No matter what k is, an obvious necessary condition for k-rectilinearity is that thedegree of each vertex does not exceed four.Our main result is that every planar graph H satisfying this condition is 3--rectilinear:in fact,it is 2--rectilinear with the only exception of the octahedron. We also outline a polynomial-timealgorithm which actually constructs a plane embedding of H with at most 2 bends (3 bends if H isthe octahedron) on each edge. The resulting embedding has the property that the total number ofbends does not exceed 2n, where n is the number of vertices of H. 展开更多
关键词 LINE GENERAL THEORETICAL RESULTS ON rectilinear EMBEDABILITY OF GRAPHS
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部