No description available.

Many countries are reporting of difficulties in exact education at schools: mathematics, informatics, physics etc. Various methods are proposed to awaken and preserve students’ interest in these disciplines. Among them, the simplification, accent on applications, avoiding of argumentation (especially in mathematics) etc. must be mentioned. As one of reasons for these approaches the growing amount of knowledge/skills to be acquired at school is often mentioned. In this paper we consider one of the possibilities to integrate partially teaching of important chapters of discrete mathematics and informatics not reducing the high educational standards. The approach is based on the identification and mastering general combinatorial principles underlying many topics in both disciplines. A special attention in the paper is given to the so-called “pigeonhole principle” and its generalizations. In folklore, this principle is usually formulated in the following way: “if there are n + 1 rabbits in n cages, you can find a cage with at least two rabbits in it“. Examples of appearances of this principle both in mathematics and in computer science are considered.

Zugl.: Bern, Univ., Diss., 2005

It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms. / Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu färben, ist als NP-vollständig bekannt. Hier werden einige Algorithmen vorgestellt, die für dieses Problem eine gute Approximation liefern. Des Weiteren wird ein allgemeines Färbungsverfahren hergeleitet, das für k-färbbare Graphen den bisher besten existierenden Algorithmus darstellt. Es können k-färbbare Graphen mit ~O(n^a(k)) Farben gefärbt werden, wobei a(2)=0, a(3)=3/14 und a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für k >= 4 gilt [20]. Diese Formel wurde für neue Basisalgorithmen verallgemeinert.

There are several different algorithms available to perform a synchronization of multiple processors. Some of them support only shared memory architectures or very fine grained supercomputers. This work gives an overview about all currently known algorithms which are suitable for distributed shared memory architectures and message passing based computer systems (loosely coupled or coarse grained supercomputers). No absolute decision can be made for choosing a barrier algorithm for a machine. Several architectural aspects have to be taken into account. The overview about known barrier algorithms given in this work is mostly targeted to implementors of libraries supporting collective communication (such as MPI).

Beim analogen Schaltungsentwurf werden zur Dimensionierung der Bauelemente Optimierungstools eingesetzt, um eine optimale Performance und maximale Robustheit zu erreichen. Beginnend mit einer Anfangslösung berechnen diese Tools iterativ bessere Lösungen. Dabei kann eine gute Anfangslösung die Rechenzeit stark verkürzen und den Optimierungserfolg verbessern. Untersuchungen haben gezeigt, dass die Optimierung wesentlich leichter zu beherrschen ist, wenn an den Bauelementen bestimmte DC-Bedingungen (Constraints) erfüllt sind. In diesem Beitrag wird gezeigt, wie durch graphentheoretische Ansätze die optimalen Knotenspannungen und Zweigströme mit geringem Rechenaufwand ermittelt werden und daraus die Dimensionierung der Bauelemente als gute Startlösung für Optimierungstools berechnet wird.

Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.:Mathematics and biology - having nothing in common? I. Going for a start 1. Introducing haplotyping 2. Becoming mathematical II. The MRS problem 3. The graph theoretical point of view 3.1. The MRS problem 3.2. The MRS problem on special graph classes 4. Trying to be not that bad 4.1. Greedy approaches 4.2. The local colour density 4.3. MaxNewColour 5. What is real data telling us? And the work goes on and on Bibliography

Many countries are reporting of difficulties in exact education at schools: mathematics, informatics, physics etc. Various methods are proposed to awaken and preserve students’ interest in these disciplines. Among them, the simplification, accent on applications, avoiding of argumentation (especially in mathematics) etc. must be mentioned. As one of reasons for these approaches the growing amount of knowledge/skills to be acquired at school is often mentioned. In this paper we consider one of the possibilities to integrate partially teaching of important chapters of discrete mathematics and informatics not reducing the high educational standards. The approach is based on the identification and mastering general combinatorial principles underlying many topics in both disciplines. A special attention in the paper is given to the so-called “pigeonhole principle” and its generalizations. In folklore, this principle is usually formulated in the following way: “if there are n + 1 rabbits in n cages, you can find a cage with at least two rabbits in it“. Examples of appearances of this principle both in mathematics and in computer science are considered.

In this thesis, we will study the concept of k-edge connected and k-connected reliability. There, vertices are modelled as fail-safe and edges fail stochastically independent. For a fixxed k, the network is then considered operational when each pair of vertices has k edge disjoint or internally disjoint paths, respectively, connecting them in the surviving subnetwork. Thus, the property of being operating covers the connectivity of the surviving graph together with some minimum bandwidth. We study essential and irrelevant edges for those reliability measures. Further, we study a splitting approach to transform the reliability of the graph into the probability that subgraphs have a certain connectivity. We also extend an approximation algorithm of Karger from the All-Terminal Unreliability to k-edge connected Unreliability and study the k-edge connected Reliability for some special graph classes, namely graphs with restricted treewidth, edge-transitive graphs and the complete graph.:1 Introduction 2 Monotone Systems 2.1 Monotone Binary Systems 2.2 Monotone Multistate Systems 3 Graphs and Graph Operations 4 Higher Connectivity 4.1 Connectivity Number and Edge-Connectivity Number 4.2 Algorithms 5 Essential and Irrelevant Edges 6 Probabilistic Graphs and Reliability Measures 7 Reductions 8 Splitting 8.1 Some Special Cases for Small Separators/Cuts 8.2 Generalization to Arbitrary Separators 8.3 Constructing the Splitting Classes for 2-ec, 3-ec and 2-vc 8.4 Minimality 8.5 A Lattice-based Approach 9 An Approximation Scheme 9.1 Definition of Approximation Algorithms 9.2 The FPRAS for All-Terminal-Unreliability 9.3 Improved Bound for the Number of alpha-cuts 9.4 Extension to k-edge-connected Unreliability 10 Special Graph Classes 10.1 Graphs with Bounded Treewidth 10.2 Edge-Transitive Graphs 10.3 The Complete Graph 11 Future Research 12 Summary

Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.