From marcus@math.tu-berlin.de Wed Feb 25 14:57:58 1998
Date: Wed, 25 Feb 1998 14:57:56 +0100
X-Sender: marcus@mail.math.tu-berlin.de
Mime-Version: 1.0
Content-Transfer-Encoding: quoted-printable
To: ando@zib.de
From: marcus@math.tu-berlin.de (Sabine Marcus)
Subject: Vortragsank"undigung


               VORTRAGSANK"UNDIGUNG im Oberseminar
---------------------------------------------------
               Kazutoshi Ando (Konrad-Zuse-Zentrum) h"alt

am             Mittwoch, 4. März 1998
um             10:30 Uhr
im             MA 645

               einen Vortrag "uber

Title: A reduction technique for some optimization problems on bidirected
graphs and relations to bisubmodular functions.

Abstract: We consider the problem of finding a minimum-weight ideal of a
bidirected graph. We associate an ordinary directed graph $\tilde{G}$ with
bidirected graph $G$ and show that the minimum-weight ideal problem on $G$
is reduced to that on $\tilde{G}$.
   The same reduction scheme is applied to solve the minimum cut problems for
bidirected graphs. It is shown that for any bidirected graph $G$ with
capacities $c(a)$ on each arc $a$ of $G$ the cut function of $G$ is
bisubmodular and that the function can be represented by the cut function of
$\tilde{G}$.

gez. Prof. Dr. Rolf H. M"ohring



              _/_/_/_/  _/_/_/_/  _/_/_/_/  _/_/_/_/
              _/          Sabine Marcus           _/
              _/     TU Berlin, FB 3, MA 6-1      _/
              _/    Stra\3e des 17. Juni 136      _/
              _/        D-10623 Berlin            _/
              _/_/_/_/  _/_/_/_/  _/_/_/_/  _/_/_/_/
              _/     phone  +49 30 314 25728      _/
              _/     fax    +49 30 314 25191      _/
              _/  e-mail marcus@math.tu-berlin.de _/
              _/_/_/_/  _/_/_/_/  _/_/_/_/  _/_/_/_/