tr-announce May 2006

tr-announce@lists.rwth-aachen.de

1 participants
3 discussions

2006-08: Optimal Vertex Elimination in Single-Expression-Use Graphs

by Peter Schneider-Kamp

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.

18 years, 3 months

2006-07: Transforming structures by set interpretations

by Peter Schneider-Kamp

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.

18 years, 3 months

2006-06: Divide-and-Color

by Peter Schneider-Kamp

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.

18 years, 3 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce May 2006