For circuit designs in advanced technologies, standard-cell libraries consist of cells with different heights; for example, the number of fins determines the height of cells in the FinFET technology. Cells of larger heights give higher drive strengths, but consume larger areas and power. Such mixed cell heights incur new, complicated challenges for layout designs, due mainly to the heterogeneity in cell dimensions and thus their larger solution spaces. There is not much published work on layout designs with mixed-height standard cells. This paper addresses the legalization problem of mixed-height standard cells, which intends to place cells without any overlap and with minimized displacement. We first study the properties of Abacus, generally considered the best legalization method for traditional single-row-height standard cells but criticized not suitable for handling the new challenge, analyze the capability and insufficiencies of Abacus for tackling the new problem, and remedy Abacuss insufficiencies and extend its advantages to develop an effective and efficient algorithm for the addressed problem. For example, dead spaces become a critical issue in mixed-cell-height legalization, which cannot be handled well with an Abacus variant alone. We thus derive a dead-space-aware objective function and an optimization scheme to handle this issue. Experimental results show that our algorithm can achieve the best wirelength among all published methods in reasonable running time, e.g., about 50% smaller wirelength increase than a state-of-the-art work.

The common objective of very large-scale integration (VLSI) placement problem is to minimize the total wirelength, which is calculated by the total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable, various differentiable wirelength approximation functions have been proposed in analytical placement methods. In this paper, we reformulate the HPWL as an l1-norm model of the wirelength function, which is exact but nonsmooth. Based on the l1-norm wirelength model and exact calculation of overlapping areas between cells and bins, a nonsmooth optimization model is proposed for the VLSI global placement problem, and a subgradient method is proposed for solving the nonsmooth optimization problem. Moreover, local convergence of the subgradient method is proved under some suitable conditions. In addition, two enhanced techniques, i.e., an adaptive parameter to control the step size and a cautious strategy for increasing the penalty parameter, are also used in the nonsmooth optimization method. In order to make the placement method scalable, a multilevel framework is adopted. In the clustering stage, the best choice clustering algorithm is modified according to the l1-norm wirelength model to cluster the cells, and the nonsmooth optimization method is recursively used in the declustering stage. Comparisons of experimental results on the International Symposium on Physical Design (ISPD) 2005 and 2006 benchmarks show that the global placement method is promising.

A graph $G$ is said to satisfy the Vizing bound if $\chi(G)\le \omega(G)+1$, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$, respectively. The class of graphs satisfying the Vizing bound is clearly $\chi$-bounded in the sense of Gyárfás. It has been conjectured that if $G$ is triangle-free and fork-free, where the fork is obtained from $K_{1,4}$ by subdividing two edges, then $G$ satisfies the Vizing bound. We show that this is true if, in addition, $G$ is $C_5$-free.

For a graph G, let $p(G)$ and $c(G)$ denote the number of vertices in a longest path and a longest cycle in G, respectively. In this paper, we prove that if G is a 2-connected graph G on n vertices with $p(G)=p$, where $p\geq20$, and if G has more than $\frac{1}{2}(p-2)(n-7)+13$ edges, then $p(G)-c(G)\leq1$, which implies that every longest cycle in G is a dominating cycle.

Let G be a simple graph on n vertices, $n\geq 3$. It is well known that if G satisfies the Ore condition that $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices x and y, then G has a Hamiltonian circuit, which implies that G has a nowhere-zero 4-flow. But it is not necessary for G to have a nowhere-zero 3-flow. In this paper, we prove that with six exceptions, all graphs satisfying the Ore condition have a nowhere-zero 3-flow. More precisely, if G is a graph on n vertices, $n\geq 3$, in which $d(x)+d(y)\geq n$ for every pair of nonadjacent vertices x and y, then G has no nowhere-zero 3-flow if and only if G is one of six completely described graphs.

Let C be a cycle. The square of C is the graph obtained by joining every pair of vertices of distance 2 in C. Let G be a graph on n vertices with minimum degree $\delta ( G )$. This paper proves that, if $\delta ( G ) \geq \frac{5}{7}n$, then G contains the square of a Hamiltonian cycle.

Let G be a bridgeless graph with m edges and n vertices. It is proved that the edges of G can be covered by circuits whose total length is at most $m + ( r/r - 1 )( n - 1 )$, where r is the minimum length of an even circuit (of G) of length at least 6 ($r = \infty $, if there is no such circuit). The proof suggests a polynomial-time algorithm for constructing such a cover.