@misc{Wagler2002, author = {Wagler, Annegret}, title = {Antiwebs are Rank-Perfect}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6742}, number = {02-07}, year = {2002}, abstract = {\We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect.}, language = {en} } @misc{Wolf2002, author = {Wolf, Thomas}, title = {The integration of systems of linear PDEs using conservation laws of syzygies}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6751}, number = {02-08}, year = {2002}, abstract = {The purpose of the paper is to formulate and use syzygies for systems of linear PDEs. The computation of an equivalent of a GCD for linear partial differential operators will save us their factorization which is otherwise only possible algorithmically in special cases. After showing the computation with the new and the traditional method and comparing both in the next three sections, the algorithm is explained in general and an overview is given.}, language = {en} } @misc{ReinefeldStuebenSchintkeetal.2002, author = {Reinefeld, Alexander and St{\"u}ben, Hinnerk and Schintke, Florian and Din, George}, title = {GuiGen: A Toolset for Creating Customized Interfaces for Grid User Communities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6737}, number = {02-06}, year = {2002}, abstract = {\textsf{\itshape{GuiGen}} is a comprehensive set of tools for creating customized graphical user interfaces (GUIs). It draws from the concept of computing portals, which are here seen as interfaces to application-specific computing services for user communities. While \textsf{\itshape{GuiGen}} was originally designed for the use in computational grids, it can be used in client/server environments as well. Compared to other GUI generators, \textsf{\itshape{GuiGen}} is more versatile and more portable. It can be employed in many different application domains and on different target platforms. With \textsf{\itshape{GuiGen}}, application experts (rather than computer scientists) are able to create their own individually tailored GUIs.}, language = {en} } @misc{KrumkeRambau2002, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Probieren geht {\"u}ber Studieren? Entscheidungshilfen f{\"u}r kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6723}, number = {02-05}, year = {2002}, abstract = {Die Automatisierung von innerbetrieblicher Logistik erfordert -- {\"u}ber die physikalische Steuerung von Ger{\"a}ten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollst{\"a}ndiges Wissen) sowie die Echtzeit-Problematik (beschr{\"a}nkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen {\"U}berblick {\"u}ber allgemeine Konstruktionsprinzipien f{\"u}r Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen f{\"u}r eine vorliegende Problemstellung geeignet sind.}, language = {de} } @misc{KuberekLillLitscheetal.2002, author = {Kuberek, Monika and Lill, Monika and Litsche, Stefan and Lohrum, Stefan and L{\"u}gger, Joachim and Otto, Dagmar and Rusch, Beate}, title = {Entwicklungsprojekt "KOBV-Informationsportal" : Teilprojekte der 1. Stufe}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6678}, number = {01-41}, year = {2002}, abstract = {Die KOBV-Suchmaschine hat seit ihrer Inbetriebnahme Ende 1999 entscheidend zur Verbesserung der Informationsinfrastruktur in Berlin und Brandenburg beigetragen. Auf der Basis der offenen Plattform KOBV-Suchmaschine wird die KOBV-Zentrale gemeinsam mit den Bibliotheken in den n{\"a}chsten Jahren das Dienstleistungsangebot des KOBV und seiner Bibliotheken kontinuierlich erweitern. Dabei sollen die Prinzipien des KOBV - Offenheit, Heterogenit{\"a}t und Dezentralit{\"a}t auf technischer und organisatorischer Ebene - gewahrt bleiben. Die einzelnen KOBV-Bibliotheken werden sich mit ihren Angeboten in unterschiedlicher Weise im Web positionieren. Die Integration auf regionaler Ebene kann und soll die lokalen Angebote nicht k{\"u}nstlich vereinheitlichen. Das kooperative Portal, das in der Region aufgebaut wird, ist als System geplant, in dem zentrales Portal und lokale Portale nicht hierarchisch einander zugeordnet, sondern miteinander vernetzt sind. Das \glqq KOBV-Informationsportal \grqq soll in der KOBV-Zentrale im Rahmen eines wissenschaftlichen Projektes von Mitte 2001 bis Ende 2003 aufgebaut werden. Das vorliegende Papier gibt einen ersten allgemeinen Einblick, welche Funktionen das \glqq KOBV-Informationsporta \grqq umfassen soll und stellt die Teilprojekte der 1. Stufe vor.}, language = {de} } @misc{HohageSchmidt2002, author = {Hohage, Thorsten and Schmidt, Frank}, title = {On the Numerical Solution of Nonlinear Schr{\"o}dinger type equations in fiber optics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6715}, number = {02-04}, year = {2002}, abstract = {The aim of this paper is to develop fast methods for the solution of nonlinear Schr{\"o}dinger type equations in fiber optics. Using the method of lines we have to solve a stiff system of ordinary differential equations where the eigenvalues of the Jacobian are close to the imaginary axis. This is usually done by a Split Step method. Here we consider the extrapolation of Split Step methods with adaptive order and step size control. For more complicated nonlinearities, in particular stimulated Raman scattering, Split Step methods are less efficient since symmetry is either destroyed or requires much additional effort. In this case we use implicit Runge Kutta formulas of Gauß type. The key point for the efficient implementation of these methods is that the system of nonlinear algebraic equations can be solved without setting up the Jacobian. The proposed methods are compared to other methods, in particular exponential integrators, the method of Marcuse, and the method of Blow and Wood.}, language = {en} } @misc{Wagler2002, author = {Wagler, Annegret}, title = {Relaxing Perfectness: Which Graphs are 'Almost' Perfect?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6700}, number = {02-03}, year = {2002}, abstract = {For all perfect graphs, the stable set polytope STAB\$(G)\$ coincides with the fractional stable set polytope QSTAB\$(G)\$, whereas STAB\$(G) \subset\$ QSTAB\$(G)\$ holds iff \$G\$ is imperfect. Padberg asked in the early seventies for ``almost'' perfect graphs. He characterized those graphs for which the difference between STAB\$(G)\$ and QSTAB\$(G)\$ is smallest possible. We develop this idea further and define three polytopes between STAB\$(G)\$ and QSTAB\$(G)\$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB\$(G)\$. The difference between QSTAB\$(G)\$ and the largest of the three polytopes coinciding with STAB\$(G)\$ gives some information on the stage of imperfectness of the graph~\$G\$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost'' perfect?}, language = {en} } @misc{PfeifleRambau2002, author = {Pfeifle, Julian and Rambau, J{\"o}rg}, title = {Computing Triangulations Using Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6692}, number = {02-02}, year = {2002}, abstract = {Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework.}, language = {en} } @misc{HohageSchmidtZschiedrich2002, author = {Hohage, Thorsten and Schmidt, Frank and Zschiedrich, Lin}, title = {A new method for the solution of scattering problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6683}, number = {02-01}, year = {2002}, abstract = {We present a new efficient algorithm for the solution of direct time-harmonic scattering problems based on the Laplace transform. This method does not rely on an explicit knowledge of a Green function or a series representation of the solution, and it can be used for the solution of problems with radially symmetric potentials and problems with waveguides. The starting point is an alternative characterization of outgoing waves called \emph{pole condition}, which is equivalent to Sommerfeld's radiation condition for problems with radially symmetric potentials. We obtain a new representation formula, which can be used for a numerical evaluation of the exterior field in a postprocessing step. Based on previous theoretical studies, we discuss the numerical realization of our algorithm and compare its performance to the PML method.}, language = {en} } @phdthesis{Eisenblaetter2001, author = {Eisenbl{\"a}tter, Andreas}, title = {Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10132}, year = {2001}, abstract = {Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.}, language = {en} } @misc{AardalHoeselKosteretal.2001, author = {Aardal, Karen I. and Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Mannino, Carlo and Sassano, Antonio}, title = {Models and Solution Techniques for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6667}, number = {01-40}, year = {2001}, abstract = {{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.}, language = {en} } @misc{BodlaenderKosterEijkhofetal.2001, author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Eijkhof, Frank van den and Gaag, Linda C. van der}, title = {Pre-processing for Triangulation of Probabilistic Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6655}, number = {01-39}, year = {2001}, abstract = {The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.}, language = {en} } @misc{KosterBodlaenderHoesel2001, author = {Koster, Arie M.C.A. and Bodlaender, Hans L. and Hoesel, Stan P.M. van}, title = {Treewidth: Computational Experiments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6644}, number = {01-38}, year = {2001}, abstract = {Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed \$k\$, linear time algorithms exist to solve the decision problem ``treewidth \$\leq k\$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.}, language = {en} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {Numerical Evaluation of SBmethod}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6637}, number = {01-37}, year = {2001}, abstract = {We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7\$^{th}\$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.}, language = {en} } @misc{Kuberek2001, author = {Kuberek, Monika}, title = {Der KOBV - eine regionale Service-Einrichtung f{\"u}r Nutzer und Bibliothekare}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6620}, number = {01-36}, year = {2001}, abstract = {Dem vorliegenden Aufsatz liegt ein Vortrag zugrunde, den die Verfasserin auf der Ersten Gemeinsamen Fachtagung der DBV-Landesverb{\"a}nde Berlin und Brandenburg "Wir machen den Weg frei : Fusionen - Kooperationen in Berlin und Brandenburg" am 17. Oktober 2001 gehalten hat, in der Vortragsreihe "M{\"o}glichkeiten und Grenzen von Ausleih- und bibliographischen Verb{\"u}nden - V{\"O}B Berlin, V{\"O}B Brandenburg, KOBV". Der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) ist angetreten, um auf der Basis neuer Technologien zeitgem{\"a}ße, nutzerorientierte Dienstleistungen f{\"u}r den Informationsbereich zu entwickeln und die Informationsinfrastruktur in der Region Berlin-Brandenburg neu zu organisieren. Dabei setzt der KOBV insbesondere auf das Internet. Die Verfasserin beschreibt die einzelnen Stufen, in denen die Dienste des KOBV aufgebaut wurden und kontinuierlich weiter ausgebaut werden. Dabei zeigt sie Vorteile auf, die Nutzern und Bibliotheken durch den Verbund entstehen, und lotet gleichzeitig die Grenzen aus, die dem Verbund gesetzt sind.}, language = {de} } @misc{BrandtBrandt2001, author = {Brandt, Andreas and Brandt, Manfred}, title = {Individual Overflow and Freed Carried Traffics for a Link with Trunk Reservation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6615}, number = {01-35}, year = {2001}, abstract = {Two traffic streams \$\Phi_1\$, \$\Phi_2\$ are offered a link. The calls of \$\Phi_i\$ require exponential holding times with parameter \$\mu\$ and are accepted if less than \$C_i\$ trunks are occupied. Approximating the \$\Phi_i\$ by appropriate renewal processes meeting their first two moments, defined as the moments of the numbers of calls in virtual links of infinite capacity to which the traffic streams as freed traffics are virtually directed and where the calls get fresh exponential i.i.d.\ holding times with parameter \$\mu\$, stable recursive algorithms of complexity \$O(\max(C_1,C_2))\$ are derived for the first two defined as above moments of the individual overflow and freed carried traffics. The results offer a unified handling of both overflow and carried traffics in circuit switching networks with trunk reservation, providing a basis for new two-moment network dimensioning algorithms.}, language = {en} } @misc{SokolovWolf2001, author = {Sokolov, Vladimir V. and Wolf, Thomas}, title = {Classification of integrable polynomial vector evolution equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6601}, number = {01-34}, year = {2001}, abstract = {Several classes of systems of evolution equations with one or two vector unknowns are considered. We investigate also systems with one vector and one scalar unknown. For these classes all equations having the simplest higher symmetry are listed.}, language = {en} } @misc{IlgenfritzKerlerMuellerPreusskeretal.2001, author = {Ilgenfritz, Ernst-Michael and Kerler, Werner and M{\"u}ller-Preussker, Michael and St{\"u}ben, Hinnerk}, title = {Parallel tempering in full QCD with Wilson fermions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6593}, number = {01-33}, year = {2001}, abstract = {We study the performance of QCD simulations with dynamical Wilson fermions by combining the Hybrid Monte Carlo algorithm with parallel tempering on \$10^4\$ and \$12^4\$ lattices. In order to compare tempered with standard simulations, covariance matrices between sub-ensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter \$\kappa\$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.}, language = {en} } @misc{ZoecklerReinBrandtetal.2001, author = {Z{\"o}ckler, Malte and Rein, Karlheinz and Brandt, Robert and Stalling, Detlev and Hege, Hans-Christian}, title = {Creating Virtual Insect Brains with Amira}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6589}, number = {01-32}, year = {2001}, abstract = {By combining techniques of preparation, histology, confocal microscopy, data visualization and data processing, we have created and recently published a standard brain model for drosophila and honey bee brains. This report describes the algorithms and implementation of the corresponding software modules. At the same time it serves as a user's guide for scientist who want to reproduce the results for differerent species or mutants.}, language = {en} } @misc{KoberSaderZeilhoferetal.2001, author = {Kober, Cornelia and Sader, Robert and Zeilhofer, Hans-Florian and Prohaska, Steffen and Zachow, Stefan and Deuflhard, Peter}, title = {Anisotrope Materialmodellierung f{\"u}r den menschlichen Unterkiefer}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6574}, number = {01-31}, year = {2001}, abstract = {Im Rahmen der biomechanischen Simulation kn{\"o}cherner Organe ist die Frage nach einer befriedigenden Materialbeschreibung nach wie vor ungel{\"o}st. Computertomographische Datens{\"a}tze liefern eine r{\"a}umliche Verteilung der (R{\"o}ntgen-)Dichte und erm{\"o}glichen damit eine gute Darstellung der individuellen Geometrie. Weiter k{\"o}nnen die verschiedenen Materialbestandteile des Knochens, Spongiosa und Kortikalis, voneinander getrennt werden. Aber die richtungsab{\"a}ngige Information der Materialanisotropie ist verloren. In dieser Arbeit wird ein Ansatz f{\"u}r eine anisotrope Materialbeschreibung vorgestellt, die es erm{\"o}glicht, den Einfluss der individuellen kn{\"o}chernen Struktur auf das makroskopische Materialverhalten abzusch{\"a}tzen.}, language = {de} } @misc{KaehlerHege2001, author = {K{\"a}hler, Ralf and Hege, Hans-Christian}, title = {Interactive Volume Rendering of Adaptive Mesh Refinement Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6561}, number = {01-30}, year = {2001}, abstract = {Many phenomena in nature and engineering happen simultaneously on rather diverse spatial and temporal scales, i.e.\ exhibit a multi-scale character. Therefore various hierarchical data structures and numerical schemes have been devised to represent quantitatively such phenomena. A special numerical multilevel technique, associated with a particular hierarchical data structure, is so-called Adaptive Mesh Refinement (AMR). This scheme achieves locally very high spatial and temporal resolutions. Due to its popularity, many scientists are in need of interactive visualization tools for AMR data. In this article we present a 3D texture-based volume rendering algorithm for AMR data, that directly utilizes the hierarchical structure. Thereby interactive rendering even for large data sets is achieved. In particular the problems of interpolation artifacts, opacity corrections, and texture memory limitations are addressed. The algorithm's value in practice is demonstrated with simulation and image data.}, language = {en} } @misc{Groetschel2001, author = {Gr{\"o}tschel, Martin}, title = {Telota - was soll das?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6538}, number = {01-27}, year = {2001}, abstract = {Telota ist ein Kunstwort, das f{\"u}r alle Aktivit{\"a}ten der Berlin-Brandenburgischen Akademie der Wissenschaften steht, die der F{\"o}rderung von Forschung, Kommunikation und Pr{\"a}sentation durch elektronische Medien dienen. In diesem Artikel werden die Entstehung des Telota-Projektes geschildert und die Ziele diskutiert, die mit diesem Projekt erreicht werden sollen. Es geht darum, moderne Informationstechnik bewusst, geplant und nachhaltig f{\"u}r alle Belange der {\rm BBAW} einzusetzen. Informationstechnische Werkzeuge sollen f{\"u}r die wissenschaftliche Arbeit effizient genutzt werden; die Information nach innen und nach außen soll deutlich verbessert werden; eine bessere Kommunikationsinfrastuktur soll die Zusammenarbeit f{\"o}rdern.}, language = {de} }