Transforming an arbitrary (min,+) problem into a binary one.

                         D.Schlesinger 

                  schles@ics.inf.tu-dresden.de

Abstract:

In our talk we consider a series of labeling problems. They emerge as
a part of general structural recognition problems especially for
complex objects that are completely interpretable by naming its
elementary parts. As a motivation we give a short overview of
practical applications, that can be naturally formulated as labeling
problems.

We will focus on so called (min,+) problems of second order. There are
several well known results for (min,+) problems with binary label
sets.  We extend these to the general case of more than two
labels. This is done by transforming an arbitrary (min,+) problem into
a binary one.

As an example we consider a class of polynomial solvable (min,+)
problems, that can be solved efficiently using such transformation.