May 2006 - tr-announce - lists.rwth-aachen.de

2006-08: Optimal Vertex Elimination in Single-Expression-Use Graphs
by Peter Schneider-Kamp 24 May '06

24 May '06

The following technical report is available from http://aib.informatik.rwth-aachen.de: Optimal Vertex Elimination in Single-Expression-Use Graphs Uwe Naumann, Yuxiao Hu AIB 2006-08 Gradients of scalar multivariate functions can be computed by elimination methods on the linearized computational graph. The combinatorial optimization problem that aims to minimize the number of arithmetic operations performed by the elimination algorithm is known to be NP-complete. In this paper we present a polynomial algorithm for solving a relevant subclass of this problem's instances. The proposed method relies on the ability to compute vertex covers in bipartite graphs in polynomial time. A simplified version of this graph algorithm is used in a research prototype of the differentiation-enabled NAGWare Fortran compiler for the preaccumulation of local gradients of scalar assignments in the context of automatic generation of efficient tangent-linear code for numerical programs.

1 0

2006-07: Transforming structures by set interpretations
by Peter Schneider-Kamp 23 May '06

23 May '06

The following technical report is available from http://aib.informatik.rwth-aachen.de: Transforming structures by set interpretations Thomas Colcombet, Christof Löding AIB 2006-07 We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of elements of the orignal structure. The definition of these interpretations directly implies that they send structures with a decidable WMSO theory to structures with a decidable first-order theory. In this paper, we investigate the expressive power of such interpretations applied to infinite deterministic trees. The results can be used in the study of automatic and tree-automatic structures.

1 0

2006-06: Divide-and-Color
by Peter Schneider-Kamp 18 May '06

18 May '06

The following technical report is available from http://aib.informatik.rwth-aachen.de: Divide-and-Color Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith AIB 2006-06 We introduce divide-and-color, a new technique for the solution of hard graph problems. It is a combination of the well-known divide-and-conquer paradigm and color-coding. Our approach first randomly colors all edges or nodes of a graph black and white, and then solves the problem recursively on the two induced parts. We demonstrate this technique by giving new randomized algorithms for the solution of two important problems. These yield runtime bounds of O*(4^k) for finding a simple path of length k and O*(4^((h-1)k)) for finding k edge-disjoint (resp. vertex-disjoint) copies of a graph H with h edges (resp. h nodes) in a given graph. Derandomization gives deterministic algorithms for these problems with running times O*(2^(4k))$ and O*(2^(4hk))$, respectively. All these results significantly improve over the currently known best bounds. In particular, our generic algorithms beat specialized ones that have been designed to find k triangles or paths of length two.

1 0