DMF's Annual Meeting 2002

Increasing the Edge-connectivity of a Graph without Adding Forbidden Edges

Jørgen Bang-Jensen
Department of Mathematics and Computer Science
University of Southern Denmark
<jbj@imada.sdu.dk>

Keywords: edge-connectivity, connectivity augmentation, flows, legal ordering, splitting, simple graph, partition constrained augmentation

The edge-connectivity of a graph G=(V,E) is the minimum number of edges one has to remove to obtain a new graph G'=(V,E') which is not connected. The problem of finding the edge-connectivity of a given graph has an efficient solution, either using techniques from network flows, or the recent edge-connectivity algorithm by Nagamochi and Ibaraki which calculates the edge-connectivity of a given graph without using any max-flow calculations. In many applications one starts with a graph G of a certain edge-connectivity l and wishes to increase the edge-connectivity of G to a certain number k>l by adding new edges to the graph. The goal is to use as few new edges as possible (the weighted version is NP-complete, even for weights 0 and 1). This is called the edge-connectivity augmentation problem. There are several polynomial algorithms for this problem and these either use the so-called splitting techniques by Lovász and Mader, or the successive augmentation approach which uses the so-called cactus. Both of these approaches have the drawback that the optimal set of new edges cannot be easily controlled, for example the new set of edges may contain many parallel edges. In this talk we will first discuss the solution of the edge-connectivity augmentation problem when one uses the splitting technique and then we shall consider two variations of the edge-connectivity augmentation problem, one in which we require that both the starting graph G and the final graph G=(V,E+F) is simple (i.e. it contains no parallel edges) and one in which we are given a partition P of V and we are not allowed to add any edges inside a partition class (i.e. each new edge goes between two distinct partition classes). It turns out that the second problem can be solved in polynomial time and that the first problem is NP-complete if k is part of the input, but for fixed k there exists a polynomial algorithm to find the minimum number of new edges to be added. The solutions of both problems are based on extensions of the splitting-technique. We illustrate the ideas to the extend that time allows.

This is joint work with Jordán respectively, Gabow, Jordán and Szigeti.

Stability of Nonlinear Systems based on Quadratic Constraints

Anton Shiriaev
Mærsk Institute
University of Southern Denmark
<anton@mip.sdu.dk>

The talk suggests a discussion of one of key results in the mathematical control theory - the quadratic stability criterion developed by Prof. V. A. Yakubovich in the 60's and 70's. A number of motivating examples are shown, and possible extensions of the result are discussed.

Homogeneous Einstein metrics and simplicial complexes

Christoph Böhm
Mathematisches Seminar der
Christian-Albrechts-Universität zu Kiel
<boehm@math.uni-kiel.de>

A compact homogeneous space is a compact manifold M acted on transitively by a compact group G of diffeomorphisms. A smooth Riemannian metric g on M is called Einstein, if the Ricci tensor of g and the metric g itself are proportional, that is if ric(g)=Cg for a constant C. In general the Einstein equation ric(g)=Cg is a complicated system of second order partial differential equations on M.

In this talk we restrict our attention to Einstein metrics g, such that G acts on the Riemannian manifold (M,g) by isometries. Due to this symmetry assumption the Einstein equation becomes a complicated system of algebraic equations. Even though for some homogeneous spaces this system can be solved explicitly in general this seems to be impossible.

By the work of Hilbert it is known that homogeneous Einstein metrics on compact homogeneous spaces are characterized variationally by the Hilbert action. We will report on how global variational methods can be applied in order to obtain very general existence results on homogeneous Einstein metrics. For instance, a simplicial complex can be assigned to every compact homogeneous space whose non-contractibility is a sufficient condition for the existence of homogeneous Einstein metrics.

Mathematics, Numerics, and Applications of Coupled Field Theory

Roderick Melnik
Mads Clausen Institute
University of Southern Denmark
<rmelnik@mci.sdu.dk>

All material systems interact in some way with their environment, and a given material system may be of any degree of complexity with components interacting with each other. When a mathematical model for such a system is constructed it is our skills, experience and our prior scientific knowledge of the system that allow us to decide on the form and relative importance of these interactions. In this talk I will focus on the mathematical modelling of coupled systems whose components interact dynamically so that their response should be obtained concurrently. One of the examples that will be discussed is aimed at a systematic description of nonlinear behaviour of materials with memory, in particular shape memory alloys. I will also demonstrate some results of computational experiments with models ranging from macroscopic climate models to models of sub-micron semiconductors and quantum devices which are unified by the fact that dynamic coupling effects keep the key to a better understanding of phenomena and processes involved.