On partitioning a graph into two connected subgraphs

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known as the 2-Disjoint Connected Subgraphs problem. It is already NP-complete for the class of n-vertex graphs G=(V,E) in which Z₁ and Z₂ each contain a connected set that dominates all vertices in V?(Z₁∪Z₂). We present an O^∗(1.2051ⁿ) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O^∗(1.2051ⁿ) time for the classes of n-vertex P₆-free graphs and split graphs. This is an improvement upon a recent O^∗(1.5790ⁿ) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer.     

一种基于Cayley图的确定性小世界网络的研究

提出了一种以Cayley图为基础的确定性小世界网络模型（CayDSW），该模型具有较高的聚类性和较小的网络直径；然后分析了该网络模型的一些主要性质并给出了路由算法；最后通过实验证明了该模型符合小世界的特性。     

Precise numerical evaluation of the two loop sunrise graph Master Integrals in the equal mass case

We present a double precision routine in Fortran for the precise and fast numerical evaluation of the two Master Integrals (MIs) of the equal mass two-loop sunrise graph for arbitrary momentum transfer in d=2 and d=4 dimensions. The routine implements the accelerated power series expansions obtained by solving the corresponding differential equations for the MIs at their singular points. With a maximum of 22 terms for the worst case expansion a relative precision of better than a part in 10¹⁵ is achieved for arbitrary real values of the momentum transfer.

Program summary

Title of program:sunemVersion: 1.0Release: 1Catalogue identifier: ADYC_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADYC_v1_0Program obtainable from:http://www-ttp.physik.uni-karlsruhe.de/Progdata/Computers: allOperating system: allProgram language used:FORTRAN77No. of lines in distributed program, including test data, etc.:1080No. of bytes in distributed program, including test data, etc.: 11 835Memory required to execute: Size: 1532KNo. of bits in a word: up to 32No. of processors used: 1Distribution format: tar.gzOther programs called: noneExternal files needed: noneNature of the physical problem: Numerical evaluation of the two Master Integrals of the equal mass two-loop sunrise Feynman graph for arbitrary momentum transfer in d=2 and d=4 dimensions.Method of solution: Accelerated power series expansions obtained by solving the differential equations for the MIs at their singular points. With a maximum of 22 terms for the worse case expansion a relative precision of better than a part in 10¹⁵ is achieved for arbitrary real values of the momentum transfer.Restrictions on complexity of the problem: Limited to real momentum transfer and equal internal masses.Typical running time: Approximately 1 μs to evaluate the four Master integrals for a fixed momentum transfer value on a Pentium IV/3 GHz Linux PC.     

Mapping two complete binary trees into the star graph with quick fault recovery

This paper proposes an approach for embedding two complete binary trees (CBT) into ann-dimensional star graph (S _n), and provides a fault-tolerant scheme for the trees. First, aCBT with height Σ _m=2 ⁿ ?logm? is embedded into theS _n with dilation 3. The height of theCBT is very close to ?Σ _m=2 ⁿ logm?, the height of the largest possibleCBT which can be embedded into theS _n. Shifting the firstCBT by generating function productg ₂ g ₃ g ₄ g ₃, anotherCBT with height Σ _m=2 ⁿ ?logm? can also be embedded into theS _n without conflicting with the first one. Moreover, if three-eights of nodes in the firstCBT and all nodes in the secondCBT are faulty, all of them can be recovered. Under the condition that the firstCBT with smaller height (?Σ _m=2 ⁿ logm? ? 1) is embedded, all the replacement nodes will be free. As a consequence, even in the case that all nodes in the two trees are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 5.     

RSA密码系统小CRT解密指数的攻击分析

本文旨在讨论使用中国剩余定理(CRT)表示解密指数的RSA系统.由于中国剩余定理表示可被用来提高计算速度,这样的系统具有很高的实际应用价值.文中主要分析当前文献中一个对具有小CRT解密指数的RSA系统的攻击.本文指出,该攻击巧妙地运用了格理论,但其中某些论断一般是不正确的,并为此提供了几个反例.本文改进并完善了这个小CRT解密指数的攻击方法.     

On the computer generation of the Erlang and negative binomial distributions with shape parameter equal to two

We provide closed-form expressions for the quantile functions of the Erlang and negative binomial distributions with shape parameter equal to two. These expressions are related to the Lambert W function.     

On an elementary application of graph theory to a magnetic survey adjustment system

A classification problem which has arisen during the design of a magnetic survey profile-adjustment system is discussed. The problem is seen to be equivalent to a standard problem in combinatories —that of determining the maximum independent set of a given undirected graph. This problem is NP-complete with probable exponential computer-time requirements, and it therefore is intractable except for the smallest of graphs. An acceptable alternative is to determine a large, maximal (but not necessarily maximum) independent set, which can be done efficiently by the simple algorithm presented here.     

On two more eigenvalue methods for an alternating sequential parallel system

The methods of Jacobi, Givens and Householder were adapted for an “Alternating Sequential Parallel”, the ASP-system in [1]; the poer, inverse-power and the bisection method (using Sturm sequences) in [2]. This shrot paper extends the collection of methods. Section 1 describes the simultaneous vector-iteration method, shows a modification for thue normal uniprocesor execution and an adaptation for ASP. In Section 2, the historically important method of Levlerrrier is parallelized because of two reasons: It exemplifies a general approach of solving problems on the ASP and can be used also for the Krylov, Danilewski or Lanczos methods which are gaining importane lately. This paper is a continuation of [1] and uses the same notation.     

On two sequences of sets of mappings of abstract sets into a Dedekind ring

This paper establishes some interrelations between a finite sequence of sets of mappings of an abstract set S into complete residue systems of pairwise relatively prime elements of any Dedekind ring and the corresponding sequence of sets of mappings of the set S into the complete residue system corresponding to the product of these elements. A relationship is revealed between the established interrelation and Lang’s theorem on isomorphic factor rings. A string model is presented that is an interpretation of structures investigated in the cases of the ring of integers and a one-element set S. It is shown that the results obtained can be used for computing the number of combinatorial objects defined in terms of finite residue rings.     

On an alternative formulation of the Fisher criterion that overcomes the small sample problem

In two very recently published rapid and brief communications, both from the same authors, an alternative formulation of the well-known Fisher criterion is presented in order to overcome the ‘small sample problem’. A theorem in the first of the two communications provides the basis for the equivalence of both formulations.By providing a simple counterexample, we disprove the theorem. Subsequently, based on an illustrative example, we demonstrate that their criterion differs from the classical one and argue that the proposed criterion is not a suitable measure of discriminability.     

On the oscillating motion of an Oldroyd-B fluid between two infinite circular cylinders

Exact solutions for some oscillating motions of Oldroyd-B fluids, between two infinite coaxial circular cylinders, are established by means of the Laplace transform. These solutions, presented as sum of the steady-state and transient solutions describe the motion of the fluid at small and large times and reduce to the similar solutions for Maxwell, second grade and Newtonian fluids as limiting cases. After some time, when the transients disappear, the starting solutions tend to the steady-state solutions which are periodic in time and independent of the initial conditions. The required time to obtain the steady-state for the cosine and the sine oscillations of the boundary is determined by graphical illustrations. This time decreases if the frequency of the velocity of the boundary increases.