KLUEDO | Search

Heuristics for the K-Cardinality Tree and Subgraph Problems (1996)

Matthias Ehrgott Horst. W. Hamacher J. Freitag F. Maffioli

In this paper we consider the problem of finding in a given graph a minimal weight subtree of connected subgraph, which has a given number of edges. These NP-hard combinatorial optimization problems have various applications in the oil industry, in facility layout and graph partitioning. We will present different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree. Both the edge- and node weighted case are investigated and extensive numerical results on the behaviour of the heuristics compared to optimal solutions are presented. The best heuristic yielded results within an error margin of less than one percent from optimality for most cases. In a large percentage of tests even optimal solutions have been found.

On a Kinetic Model for Shallow Water Waves (1993)

Jens Struckmeier

The system of shallow water waves is one of the classical examples for nonlinear, twodimensional conservation laws. The paper investigates a simple kinetic equation depending on a parameter e which leads for e to 0 to the system of shallow water waves. The corresponding equilibrium distribution function has a compact support which depends on the eigenvalues of the hyperbolic system. It is shown that this kind of kinetic approach is restricted to a special class of nonlinear conservation laws. The kinetic model is used to develop a simple particle method for the numerical solution of shallow water waves. The particle method can be implemented in a straightforward way and produces in test examples sufficiently accurate results.

Factorization Theory for Stable, Discrete-Time Inner Functions (1994)

Paul A. Fuhrmann Jörg Hoffmann

We develop a factorization theory for stable inner functions relative to the unit circle.

On Balanced Realizations of Bounded Real and Positive Real Functions (1994)

Paul A. Fuhrmann Jörg Hoffmann

Based on normalized coprime factorizations with respect to indefinite metrics and the construction of suitable characteristic functions, the Ober balanced canonical forms for the classes of bounded real and positive real are derived. This uses a matrix representation of the shift realization with respect to a basis related to sets of orthogonal polynomials.

Lifetime Estimation in the Car Industry (1994)

Michael Hack

Whenever new parts of a car have been developed, the manufacturer needs an estimation of the lifetime of this new part. On one hand the construction must not be too weak, so that the part holds long enough to satisfy the customer, but on the other hand, if the construction is too excessive, the part gets too heavy.; One is interested in methods that only need few measured data from the specimen itself, but use data about the material, because constructing and testing of specimen is expensive.

Generation of Random Variates Using Asymptotic Expansions (1994)

Jens Struckmeier

Monte-Carlo methods are widely used numerical tools in various fields of application, like rarefied gas dynamics, vacuum technology, stellar dynamics or nuclear physics. A central part in all applications is the generation of random variates according to a given probability law. Fundamental techniques to generate non-uniform random variates are the inversion principle or the acceptance-rejection method. Both procedures can be quite time-consuming if the given probability law has a complicated structure.; In this paper we consider probability laws depending on a small parameter and investigate the use of asmptotic expansions to generate random variates. The results given in the paper are restrictedto first order expansions. We show error estimates for the discrepancy as well as for the bounded Lipschitz distance of the asymptotic expansion. Furthermore the integration error for some special classes of functions is given. The efficiency of the method is proved by a numerical example from rarefied gas flows.

Tutorial on Asymptotic Analysis I (1994)

Jens Struckmeier

This text summarizes parts of the exercises of the tutorialon 'Asymptotic Analysis' held in the winter term 1993/94 atthe University of Kaiserslautern.

A: New Wavelet Methods for Approximating Harmonic Functions; B: Satellite Gradiometry - from Mathematical and Numerical Point of View (1995)

Willi Freeden Michael Schreiner

Some new approximation methods are described for harmonic functions corresponding to boundary values on the (unit) sphere. Starting from the usual Fourier (orthogonal) series approach, we propose here nonorthogonal expansions, i.e. series expansions in terms of overcomplete systems consisting of localizing functions. In detail, we are concerned with the so-called Gabor, Toeplitz, and wavelet expansions. Essential tools are modulations, rotations, and dilations of a mother wavelet. The Abel-Poisson kernel turns out to be the appropriate mother wavelet in approximation of harmonic functions from potential values on a spherical boundary.

Scale-Space Properties of Nonlinear Diffusion Filtering with a Diffusion Tensor (1994)

Joachim Weickert

In spite of its lack of theoretical justification, nonlinear diffusion filtering has become a powerful image enhancement tool in the recent years. The goal of the present paper is to provide a mathematical foundation for nonlinear diffusion filtering as a scale-space transformation which is flexible enough to simplify images without loosing the capability of enhancing edges. By stuying the Lyapunow functional, it is shown that nonlinear diffusion reduces Lp norms and central moments and increases the entropy of images. The proposed anisotropic class utilizes a diffusion tensor which may be adapted to the image structure. It permits existence, uniqueness and regularity results, the solution depends continuously on the initial image, and it fulfills an extremum principle. All considerations include linear and certain nonlinear isotropic models and apply to m-dimensional vector-valued images. The results are juxtaposed to linear and morphological scale-spaces.

Boltzmann Simulation by Particle Methods (1994)

Helmut Neunzert Jens Struckmeier

Particle methods to simulate rarefied gas flows have found an increasing interest in Computational Fluid Dynamics during the last decade, see for example [1], [2], [3] and [4]. The general goal is to develop numerical schemes which are reliable enough to substitute real windtunnel experiments, needed for example in space research, by computer experiments. In order to achieve this goal one needs numerical methods solving the Boltzmann equation including all important physical effects. In general this means 3D computations for a chemically reacting rarefied gas. With codes of this kind at hand, Boltzmann simulation becomes a powerful tool in studying rarefied gas phenomena.

Refine

Faculty / Organisational entity

Author

Year of publication

Document Type

Language

Has Fulltext

Keywords

1979 search hits