In this paper we introduce an extension of the Traveling Salesman Problem (TSP), which is motivated by an important application in bioinformatics. In contrast to the TSP the costs do not only depend on each pair of two nodes traversed in succession in a cycle but on each triple of nodes traversed in succession. This problem can be formulated as optimizing a quadratic objective function over the traveling salesman polytope, so we call the combinatorial optimization problem quadratic TSP (QTSP). Besides its application in bioinformatics, the QTSP is a generalization of the Angular-Metric TSP and the TSP with reload costs. Apart from the TSP with quadratic cost structure we also consider the related Cycle Cover Problem with quadratic objective function (QCCP). In this work we present three exact solution approaches and several heuristics for the QTSP. The first exact approach is based on a polynomial transformation to a TSP, which is then solved by standard software. The second one is a branch-and-bound algorithm that relies on combinatorial bounds. The best exact algorithm is a branch-and-cut approach based on an integer programming formulation with problem-specific cutting planes. All heuristical approaches are extensions of classic heuristics for the TSP. Finally, we compare all algorithms on real-world instances from bioinformatics and on randomly generated instances. In these tests, the branch-and-cut approach turned out to be superior for solving the real-world instances from bioinformatics. Instances with up to 100 nodes could be solved to optimality in about ten minutes.

Discrete wavelet transformations (DWT) followed by embedded zerotree encoding is a very efficient technique for image compression \cite{TenLectures, Shapiro, Spiht}. However, the algorithms proposed in literature assume random access to the whole image. This makes the algorithms unsuitable for hardware solutions because of extensive access to external memory. Here, we present an efficient architecture for computing DWT of images, which is based on a partitioned approach for lossy image compression~\cite{Ritter}. The architecture achieves its computational power by using pipelining and taking advantage of the flexible memory configurations available in FPGA's.

An efficient representation of the (smoothed) transition relation of a synchronous finite state machine (FSM) speeds up the traversal based symbolic verification and the functional simulation of the FSM.When using reduced ordered binary decision diagrams (BDDs), dynamic reordering algorithms are applied in order to keep the sizes of the BDDs tractable.However, when FSMs are represented by BDDs, the state encoding can be used as an additional optimization criteria.In this paper, we present a new algorithm for state encoding of FSMs that minimizes the BDD representations of the corresponding (smoothed) transition relations.Experimental results show the approach to be very efficient.

Formal verification of integer multipliers was an open problem for a long time as the size of any reduced ordered binary decision diagram (BDD) [1] which represents integer multiplication is exponential in the width of the operands [2]. In 1995, Bryant and Chen [4] introduced multiplicative binary moment diagrams (*BMD) which are a canonical data structure for pseudo Boolean functions allowing a linear representation of integer multipliers. Based on this data structure, Bryant/Chen [4] and Hamaguchi et.al. [5] experimentally showed that integer multipliers up to a word size of 64 bits can be formally verified. However, all these results only handle the problem of proving a faultless integer multiplier to be correct. But, what happens if the multiplier is faulty? Does the backward construction method of Hamaguchi et.al. stop after a short time? After what time can I be sure that the integer multiplier under consideration is faulty? In this paper, we show that these questions are relevant in practice. In particular, we investigate simple add-step multipliers and show that simple design errors can lead to exponential growth of the *BMDS occuring during backward construction. This proves that the backward construction method can only be applied as filter during formal logic combinational verification unless sharp upper bounds for the sizes of the *BMDs occuring during the backward construction have been proven for the various circuit types as Keim et.al. [6] did it for Wallace Tree multipliers.

This paper investigates reduced ordered binary decision diagrams (OBDD) of partially symmetric Boolean functions when using variable orders where symmetric variables are adjacent. We prove upper bounds for the size of such symmetry ordered OBDDs (SymOBDD). They generalize the upper bounds for the size of OBDDs of totally symmetric Boolean functions and nonsymmetric Boolean functions proven by M.A. Heap and M.R. Mercer (1994) and I. Wegener (1984). Experimental results based on these upper bounds show that the nontrivial symmetry sets of a Boolean function should be located either right up at the beginning or right up at the end of the variable order in order to obtain best upper bounds.

In this paper we study the effect of using information about (partial) symmetries for the minimization of reduced ordered binary decision diagrams (ROBDD's). The influence of symmetries for the integration in dynamic variable ordering is studied for both completely and incompletely specified Boolean functions. The problems above are studied from a theoretical and practical point of view. Statistical results and benchmark results are reported to underline the efficiency of the approach. They prove that our techniques lead to improvements of the ROBDD sizes by up to 70%.

Until recently verifying multipliers with formal methods was not feasible, even for small input word sizes. About two years ago, a new data structure, called Multiplicative Binary Moment Diagram (*BMD), was introduced for representing arithmetic functions over Boolean variables. Based on this data structure, methods were proposed by which verification of multipliers with input word sizes of up to 256 bits became feasible. Only experimental data has been provided for these verification methods until now. In this paper we give a formal proof that logic verification using *BMDs is polynomially bounded in both space and time when applied to the class of Wallace-tree like multipliers.

This paper investigates the sizes of symmetric variable order based reduced binary decision diagrams for partially symmetric Boolean functions. It gives exact bounds for the maximum number of nonterminal vertices for the cases that the set of symmetric variables is treated as block which is located either at the front or at the back of the variable order.

No abstract available.

No abstract available.

We present a polynomial time improvement of the linear channel pin assignment LCPA algorithms presented by Cai and Wong in 1990. We solve the LCPA problem according to minimum channel density under a special priority schedule subject to vertical constraints and flux. The priority driven linear channel pin assignment algorithm (PDCPA) reduces the channel height by an average of 17% without increasing the running time.

We present a performance driven generator for integer adders which has the following interesting feature: The generator is parametrized in the operands' bitlength n, the delay of the addition t/sub n/, and the fault model FM. FM may in particular be chosen as the classical stuck-at fault model, the cellular fault model or the robust path delay fault model. The output of the generator is a performance oriented conditional sum type adder, i.e., an area-minimal n-bit adder of the "conditional sum type" with delay /spl les/t/sub n/ (if it exists) together with a small complete test set with respect to the chosen fault model FM.>

A multilevel logic synthesis technique for multi-output Boolean functions is presented which is based on minimizing the communication complexity. Unlike previous approaches, which in the final analysis decompose each single-output function f/sub i/ of a multi-output function f=(f/sub 1/, ..., f/sub m/) independently of the other single-output functions f/sub j/ (j/spl ne/i), the approach presented in this paper gives special attention to the fact that there possibly exist some decomposition functions which can be used by different outputs during the decomposition of the single-output functions of f. The benchmarking results (taken from 1991 MCNC multilevel logic benchmarks) which close the paper are promising.>

Due to progress in VLSI technology, algorithm-oriented array architectures such as systolic arrays or bit-slice structures appear to be effective, feasible, and economic. The constrained-via-minimization problem for circuits composed of arrays of identical cells C is discussed. To guarantee identical electrical behavior of all instances of C and to allow further hierarchical processing, it is desirable to handle all instances of C identically. To this end, layer assignments of circuits needing a minimal number of via holes are sought. It is shown that this problem can be solved by embedding C on the torus, i.e. by identifying the northern boundary of C with the southern boundary, and the eastern one with the western one. The time complexity of the proposed algorithm is O(m/sup 3//sub C/), where m/sub C/ is the number of routing segments in C.>

We present an algebraic approach to hierarchical design of integrated circuits. This approach is based on a of nets which includes topological as well as behavioural aspects of integrated circuits. We have developed a hierarchical design system called CADIC which is build around this calculus in much the same way as e.g. Algol is build around numerics. An example for the design of a family of fast adders will demonstrate the power of this calculus. Finally we will give a summary outline on the structure of procedures which automatically transform the design into lower design levels.