The k-fundamental group of a closed k-surface

In this paper, we deal with the problem of computing the digital fundamental group of a closed k-surface by using various properties of both a (simple) closed k-surface and a digital covering map. To be specific, let be a simple closed k_i-curve with l_i elements in Z^n_i, i∈{1,2}. Then, the Cartesian product is not always a closed k-surface with some k-adjacency of Z^n₁+n₂. Thus, we provide a condition for to be a (simple) closed k-surface with some k-adjacency depending on the k_i-adjacency, i∈{1,2}. Besides, even if is not a closed k-surface, we show that the k-fundamental group of can be calculated by both a k-homotopic thinning and a strong k-deformation retract.     

Digital fundamental group and Euler characteristic of a connected sum of digital closed surfaces

Unlike the connected sum in classical topology, its digital version is shown to have some intrinsic feature. In this paper, we study both the digital fundamental group and the Euler characteristic of a connected sum of digital closed k_i-surfaces, i∈{0,1}.     

Geometric modeling of spatial constraints: objectives, methods and solid-modeling requirements

Robust Product Lifecycle Management (PLM) technology requires availability of informationally- complete models for all parts of a design-project including spatial constraints. This is the subject of the present investigation, leading to a new model for spatial constraints, the ``virtual solid', which generalizes a similar concept used by Sapidis and Theodosiou to model ``required free-spaces' in plants [14]. The present research focuses on the solid-modeling aspects of the virtual-solid methodology, and derives new solid-modeling problems (related to object definition and to object processing), whose robust treatment is a prerequisite for developing efficient models for complex spatial constraints.     

Distribution of Lattice Points

We discuss the lattice structure of congruential random number generators and examine figures of merit. Distribution properties of lattice measures in various dimensions are demonstrated by using large numerical data. Systematic search methods are introduced to diagnose multiplier areas exhibiting good, bad and worst lattice structures. We present two formulae to express multipliers producing worst and bad laice points. The conventional criterion of normalised lattice rule is also questioned and it is shown that this measure used with a fixed threshold is not suitable for an effective discrimination of lattice structures. Usage of percentiles represents different dimensions in a fair fashion and provides consistency for different figures of merits.     

On the k-path cover problem for cacti

In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time.     

The new extended Jacobian elliptic function expansion algorithm and its applications in nonlinear mathematical physics equations

More recently we have presented the extended Jacobian elliptic function expansion method and its algorithm to seek more types of doubly periodic solutions. Based on the idea of the method, by studying more relations among all twelve kinds of Jacobian elliptic functions. we further extend the method to be a more general method, which is still called the extended Jacobian elliptic function expansion method for convenience. The new method is more powerful to construct more new exact doubly periodic solutions of nonlinear equations. We choose the (2+1)-dimensional dispersive long-wave system to illustrate our algorithm. As a result, twenty-four families of new doubly periodic solutions are obtained. When the modulus m→1 or 0, these doubly periodic solutions degenerate as soliton solutions and trigonometric function solutions. This algorithm can be also applied to other nonlinear equations.     

Volume Maximization and Orthoconvex Approximation of Orthogons

Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P. Received: September 7, 1998     

Path multicoloring with fewer colors in spiders and caterpillars

We study a recently introduced path coloring problem with applications to wavelength assignment in all-optical networks with multiple fibers. In contrast to classical path coloring, it is, in this setting, possible to assign a color more than once to paths that pass through the same edge; the number of allowed repetitions per edge is given and the goal is to minimize the number of colors used. We present algorithms and hardness results for tree topologies of special interest. Our algorithms achieve approximation ratio of 2 in spiders and 3 in caterpillars, whereas the best algorithm for trees so far, achieves an approximation ratio of 4. We also study the directed version of the problem and show that it admits a 3-approximation algorithm in caterpillars, while it can be solved exactly in spiders.