We propose a polynomial time computable graph invariant, which comes out directly from a modified version of discrete Greens function on a graph. It is our hope that it can help to construct fast algorithms for the graph isomorphism testing. We explain the physics behind this discrete Greens function, which is a very basic idea applied to graphs.

In this paper, we consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By (1) analyzing several characteristics of four types of cross cells and (2) presenting three cycle-merging operations and one extension operation, we propose an algorithm that finds in an n-vertex grid graph G, a long path of length at least 5/6 n + 2. Our approximation algorithm runs in quadratic time. In addition to its theoretical value, our work has also an interesting application in image-guided maze generation.

Let X be a compact connected strongly pseudoconvex CR manifold of real dimension 2n . 1 in CN. It has been an interesting question to find an intrinsic smoothness criteria for the complex Plateau problem. For n  3 and N = n+1, Yau found a necessary and sufficient condition for the interior regularity of the HarveyLawson solution to the complex Plateau problem by means of Kohn–Rossi cohomology groups on X in 1981. For n = 2 and N  n + 1, the problem has been open for over 30 years. In this paper we introduce a new CR invariant g(1,1)(X) of X. The vanishing of this invariant will give the interior regularity of the Harvey–Lawson solution up to normalization. In the case n = 2 and N = 3, the vanishing of this invariant is enough to give the interior regularity.

Protein universe is a complex system with critical problem of protein evolution to be analyzed. Early studies have used geometric distances and polygenetic-trees to solve this problem. However, the traditional methods are bivariate, whose taxonomy classification relies on bivariate branching. This is not sufficient to describe the complex nature of protein universe. Therefore, we propose a novel approach on multivariate protein classification. The new method bases on the theory of information and network, can be used to analyze multivariate relationships of proteins. The new method is alignment-free and have wide-applications to both sequences and 3D structures. We demonstrate the new method on six protein examples, results show that the new method is efficient and can potentially be used for future protein classifications.

No abstract uploaded!