Local Algorithms for the Prime Factorization of Strong Product Graphs

The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data. A first step towards error-tolerant “approximate” prime factorization, is the development of local approaches that cover the graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product. To this end we introduce the backbone \mathbbB (G)\mathbb{B} (G) for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors.     

On the Strong Product of a k-Extendable and an l-Extendable Graph

 Let G ₁⊗G ₂ be the strong product of a k-extendable graph G ₁ and an l-extendable graph G ₂, and X an arbitrary set of vertices of G ₁⊗G ₂ with cardinality 2[(k+1)(l+1)/2]. We show that G ₁⊗G ₂−X contains a perfect matching. It implies that G ₁⊗G ₂ is [(k+1)(l+1)/2]-extendable, whereas the Cartesian product of G ₁ and G ₂ is only (k+l+1)-extendable. As in the case of the Cartesian product, the proof is based on a lemma on the product of a k-extendable graph G and K ₂. We prove that G⊗K ₂ is (k+1)-extendable, and, a bit surprisingly, it even remains (k+1)-extendable if we add edges to it. Received: February 17, 1997 Final version received: June 14, 2000     

On a theorem of Halin

This note presents a new, elementary proof of a generalization of a theorem of Halin to graphs with unbounded degrees, which is then applied to show that every connected, countably infinite graph G, with \(\aleph _0 \le |{\text {Aut}}(G)| < 2^{\aleph _0}\) and subdegree-finite automorphism group, has a finite set F of vertices that is setwise stabilized only by the identity automorphism. A bound on the size of such sets, which are called distinguishing, is also provided. To put this theorem of Halin and its generalization into perspective, we also discuss several related non-elementary, independent results and their methods of proof.     

Calculation of the critical currents of Bi(2223)/Ag tapes and coils with reduced anisotropy in Ic(B) characteristic — effect of different proportional representations of the filaments oriented parallel and perpendicularly to the tape surface

A mathematical model was developed to allow for the prediction of critical currents in Bi(2223)/Ag-sheathed tapes that consist of two groups of filaments, having crystalline texture (c-axis) predominantly in two directions orthogonal to each other and to the length of the conductor (filaments oriented parallel and perpendicular to the tape surface). Using the theory presented, it is possible to estimate the upper limit of critical currents in the tapes prepared with a two-axial rolling technique. Magnetic field and angular dependencies of critical currents were obtained at 77 K measuring tapes with various proportional representations of filaments oriented in both preferred directions, i.e., the parallel and perpendicular directions. The results of calculation indicate that the anisotropy in the I_c(B) characteristic should be reduced considerably using the two-axial rolling. Unfortunately, the effect of anisotropy reduction is accompanied by simultaneous decrease in the current-carrying capacity of the tapes. The data obtained for short tape samples were utilised to estimate the critical currents of the individual turns of a small cylindrical magnet, assembled of eight pancake coils. It is shown that only a slight increase in the critical current of the magnet can be expected if the winding should be made of the tape with reduced anisotropy in the I_c(B) characteristic. The factors that limit the increase of the magnet critical current are discussed in detail.     

Über das lexikographische und das kostarke Produkt von Mengensystemen

Ohne Zusammenfassung     

Carbohydrate based chiral iodoarene catalysts for enantioselective dearomative spirocyclization

Organocatalysis using chiral iodoarenes enables many different enantioselective chemical reactions with cheap, easily accessible and robust catalysts. Carbohydrates have often been used as starting materials for the synthesis of chiral ligands for transition metal catalysts. Here, we now present the synthesis of the first carbohydrate based iodoarene catalysts which can be synthesized in one step starting from known compounds. These catalysts were used for oxidative spriolactonization of 3-(1-hydroxynaphthalen-2-yl)propanoic acid to afford the corresponding spirolactone in yields up to 77% and enantiomeric ratios er up to 80:20.     

A new analytical method for computing solvent-accessible surface area of macromolecules and its gradients

In the calculation of thermodynamic properties and three-dimensional structures of macromolecules, such as proteins, it is important to have an efficient algorithm for computing the solvent-accessible surface area of macromolecules. Here, we propose a new analytical method for this purpose. In the proposed algorithm we consider the transformation that maps the spherical circles formed by intersection of the atomic surfaces in three-dimensional space onto the circles on a two-dimensional plane, and the problem of computing the solvent-accessible surface area is reduced to the problem of computing the corresponding curve integrals on the plane. This allows to consider only the integrals along the circular trajectories on the plane. The algorithm is suitable for parallelization. Testings on many proteins as well as the comparison to the other analogous algorithms have shown that our method is accurate and efficient.     

Zehnpunktige Kubische Graphen

Ohne Zusammenfassung     

Das lexikographische Produkt gerichteter Graphen

Ohne Zusammenfassung