S-桥图的色惟一性

由连接两个项点的s条内部不交的路组成的图中s－桥图，记作F（k1,k2,…ks）本文讨论了此类图的色性，给出了此类图色借书证一的一个充分条件，并证明了s- 2－桥图Ft(2,2,…，2，a,b）是色惟一的。     

Travelling Wave Solution of Korteweg-de Vries-Burger's Equation

An attempt has been made to obtain exact analytical travelling wave solution of Korteweg-de Vries-Burger's (KdVB) equation by the so-called tanh-method. This equation can be derived for dust ion acoustic shocks by using reduction perturbation method. It is found that an exact solution of the KdVB equation is obtained by tanh-method, provided the parameters involved satisfy a constraint relation. However a special exact analytical solution can be obtained where no such restriction is necessary. This solution has the structure of a shock wave. Numerical solution is also obtained for travelling wave with or without the assumption of the constraint relation. We have also found a singular solution in terms of cosech and coth functions.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

A New Approach to the Algebraic Structures for Integration Methods

The analysis of compositions of Runge-Kutta methods involves manipulations of functions defined on rooted trees. Existing formulations due to Butcher [1972], Hairer and Wanner [1974], and Murua and Sanz-Serna [1999], while equivalent, differ in details. The subject of the present paper is a new recursive formulation of the composition rules. This both simplifies and extends the existing approaches. Instead of using the order conditions based on trees, we propose the construction of the order conditions using a suitably chosen basis on the tree space. In particular, the linear structure of the tree space gives a representation of the C and D simplifying assumptions on trees which is not restricted to Runge-Kutta methods. A proof of the group structure of the set of elementary weight functions satisfying the D simplifying assumptions is also given is this paper.     

一类3度正则有向图网络模型

讨论了一种3度正则网络，这类网络具有较小的网络直径，本给出了网络直径、网络支撑树和欧拉环游的数目的公式．     

空间索引的新机制——G树

研制空间数据库管理系统，提出一种Ｇ树的空间模型和动态格网的操作算法，设计实现了基于页面的新的空间索引机制，有效的解决了Ｎ维空间数据的索引问题．     

Study of the effect of capillary pressure on the permeability of porous media embedded with a fractal-like tree network

In this paper, the analytical expressions for permeability of (both saturated and unsaturated) porous media embedded with a fractal-like tree network are presented based on fractal theory and technique when the capillary pressure is taken into account. Both the dimensionless effective permeability and the relative permeability of the composites, which are defined as porous media embedded with a fractal-like tree network in this work, are derived and found to be a function of saturation, the capillary pressure and microstructural parameters of the networks. The relative permeabilities predicted by the present fractal model are compared with the available experimental data and a fair agreement between them is found.     

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.     

Sandpile groups and spanning trees of directed line graphs

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when G is regular of degree k, we show that the sandpile group of G is isomorphic to the quotient of the sandpile group of LG by its k-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.