Search

Abstract: In this paper we develop approximation algorithms for generalizations of the following three known combinatorial optimization problems, the Prize-Collecting Steiner Tree problem, the Prize-Collecting Travelling Salesman Problem and a Location-Routing problem. Given a graph on vertices and a length function on its edges, in the grouped versions of the above mentioned problems we assume that is partitioned into groups, , with a penalty function on the groups. In the Group Prize-Collecting Steiner Tree problem the aim is to find , a collection of groups of and a tree spanning the rest of the groups not in , so as to minimize the sum of the costs of the edges in the tree and the costs of the groups in . The Group Prize-Collecting Travelling Salesman Problem, is defined analogously. In the Group Location-Routing problem the customer vertices are partitioned into groups and one has to select simultaneously a subset of depots to be opened and a collection of tours that covers the customer groups. The goal is to minimize the costs of the tours plus the fixed costs of the opened depots. We give a -approximation algorithm for each of the three problems, where is the cardinality of the largest group. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in -time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of of the optimum in -time, where is the minimum k such that there is a spanning tree of the graph with maximum degree k. [Copyright &y& Elsevier]

Abstract: In this paper, we extend the algorithm in Xue and Cheng [L. Xue, X.L. Cheng, An algorithm for solving the obstacle problems, Comput. Math. Appl. 48 (2004) 1651–1657] for solving the double obstacle problem. We try to find the approximated region of the contact in the double obstacle problem with less computation time by iteration. Numerical example is given for the double obstacle problem for the elastic–plastic torsion problem to support the algorithm. [Copyright &y& Elsevier]

Abstract: The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of -colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. [Copyright &y& Elsevier]

Abstract: Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general transformation for constructing self-stabilizing algorithms which utilize distance- knowledge. Our transformation has both a slowdown and space overhead in , and might be thought of as a distance- resource allocation algorithm. Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. These results can be generalized to efficiently find maximal -sets, for properties which we call local monotonic. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information. [Copyright &y& Elsevier]

Abstract: Robust DEM co-registration for detecting terrain changes is an attractive but unresolved problem in both Remote Sensing and the Prevention and Mitigation of Hazards. Since robust DEM co-registration is an inherently very difficult problem, the algorithms developed are becoming more and more complicated. In this paper, a robust method for DEM co-registration is proposed, which integrates the least trimmed squares (LTS) estimator with the least Z-difference (LZD) algorithm. Moreover, a self-adaptive threshold based on the histogram of height differences is employed to identify the terrain changes automatically, which are the fundamental data for landslide assessment. The results of simulated experiments illustrate the robustness and accuracy of the new algorithm. [Copyright &y& Elsevier]

Abstract: The general all-ones problem is defined as follows: Given a graph , where V and E denote the vertex-set and the edge-set of G, respectively. Denote C as an initial subset of V. The problem is to find a subset X of V such that for every vertex of the number of vertices in X adjacent to is odd while for every vertex of C the number is even. X is called a solution to the problem. When , this problem is the so-called all-ones problem. If a vertex is viewed to be adjacent to itself, the all-ones problem is addressed as the all-ones problem. The all-ones problem has been studied extensively. However, the all-ones problem has received much less attention. Unlike the all-ones problem, which has solutions for any graphs, the all-ones problem may not have solutions for many graphs, even for some very simple graphs like and . So, it becomes an interesting question to find polynomial time algorithms to determine if for a given tree the problem has solutions. And if it does, to find a solution to the minimum all-ones problem. In this paper we present two algorithms of linear time to solve the general all-ones problem for trees. The first one is good for counting the number of solutions if solutions do exist, and the second one is good for solving the minimum all-ones problem. Furthermore, we can modify the algorithm slightly to solve the general minimum all-ones problem. [Copyright &y& Elsevier]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]

Abstract: In the present paper, an efficient algorithm for connectivity analysis of moderately sized distribution networks has been suggested. Algorithm is based on generation of all possible minimal system cutsets. The algorithm is efficient as it identifies only the necessary and sufficient conditions of system failure conditions in n-out-of-n type of distribution networks. The proposed algorithm is demonstrated with the help of saturated and unsaturated distribution networks. The computational efficiency of the algorithm is justified by comparing the computational efforts with the previously suggested appended spanning tree (AST) algorithm. The proposed technique has the added advantage as it can be utilized for generation of system inequalities which is useful in reliability estimation of capacitated networks. [Copyright &y& Elsevier]

Abstract: In this paper an algorithm for obtaining feedbacks to normalize variable linear systems is presented. For that, conditions to obtain an invariant singular system from a variable system are established. The relation between them is used to construct feedbacks in order to remove the impulses that disturb the behaviour of the singular system. In addition, some examples clarify the obtained results. [Copyright &y& Elsevier]

Abstract: In the present paper, the authors reject one of Knuth’s well known results on average case complexity in replacement (i.e. selection) sort and hence challenge the robustness of average complexity measures where the response variable is sensitive to ties. [Copyright &y& Elsevier]

Abstract: A minus clique-transversal function of a graph is a function such that for every clique C of G. The weight of a minus clique-transversal function is , over all vertices . The minus clique-transversal number of a graph G, denoted , equals the minimum weight of a minus clique-transversal function of G. The upper minus clique-transversal number of a graph G, denoted , equals the maximum weight of a minimal minus clique-transversal function of G. In this paper, we show that the minus clique-transversal problem (respectively, upper minus clique-transversal problem) is NP-complete even when restricted to chordal graphs. On the other hand, we give a linear algorithm to solve the minus clique-transversal problem for block graphs. [Copyright &y& Elsevier]

Theoretical geochemical models for electrolyte solutions based on classical thermodynamic principles rely largely upon molal concentrations as input because molality (wt/wt) is independent of temperature and pressure. On the other hand, there are countless studies in the literature where concentrations are expressed as molarity (wt/vol) because these units are more easily measured. To convert from molarity to molality requires an estimate of solution density. Unfortunately, in many, if not most, cases where molarity is the concentration of choice, solution densities are not measured. For concentrated brines such as seawater or even more dense brines, the difference between molarity and molality is significant. Without knowledge of density, these brinish, molar-based studies are closed to theoretical electrolyte solution models. The objective of this paper is to present an algorithm that can accurately calculate the density of molar-based solutions, and, as a consequence, molality. The algorithm consist of molar inputs into a molal-based model that can calculate density (FREZCHEM). The algorithm uses an iterative process for calculating absolute salinity , density , and the conversion factor for molarity to molality. Three cases were examined ranging in density from 1.023 to 1.203 kg(soln.)/l. In all three cases, the , , and values converged to within 1ppm by nine iterations. In all three cases, the calculated densities agreed with experimental measurements to within . This algorithm opens a large literature based on molar concentrations to exploration with theoretical models based on molal concentrations and classical thermodynamic principles. [Copyright &y& Elsevier]

Abstract: In 2006, Blake, Murty and Xu proposed three refinements to Miller’s algorithm for computing Weil/Tate pairings. In this paper we extend their work and propose a generalized algorithm, which integrates their first two algorithms. Our approach is to pre-organize the binary representation of the involved integer to the best cases of Blake’s algorithms. Further, our refinement is more suitable for Solinas numbers than theirs. We analyze our algorithm and show that our refinement has better performance than the original algorithms. [Copyright &y& Elsevier]

Abstract: In many practical situations, the ordering cost can be reduced by capital investment and the back-order rate is dependent on the amount of shortages and back-order price discounts. Hence, in this paper, we consider an inventory model with random yield in which the ordering cost can be reduced through capital investment, lead time can be shortened at an extra crashing cost and allow the back-order rate as a control variable to widen applications of Wu and Tsai’s [J.W. Wu, H.Y. Tsai, Mixture inventory model with back-orders and lost sales for variable lead time demand with the mixtures of normal distribution, International Journal of Systems Science 32 (2001) 259–268] model. Moreover, we also consider the back-order rate that proposed by combining Ouyang and Chuang [L.Y. Ouyang, B.R. Chuang, Mixture inventory model involving variable lead time and controllable backorder rate, Computers & Industrial Engineering 40 (2001) 339–348] (or Lee [W.C. Lee, Inventory model involving controllable backorder rate and variable lead time demand with the mixtures of distribution, Applied Mathematics and Computation 160 (2005) 701–717]) with Pan and Hsiao [J.C.-H. Pan, Y.C. Hsiao, Inventory models with back-order discounts and variable lead time, International Journal of Systems Science 32 (2001) 925–929; J.C.-H. Pan, Y.C. Hsiao, Integrated inventory models with controllable lead time and backorder discount considerations, International Journal of Production Economics 93–94 (2005) 387–397] (also see Pan et al. [J.C.-H. Pan, M.C. Lo, Y.C. Hsiao, Optimal reorder point inventory models with variable lead time and backorder discount considerations, European Journal of Operational Research 158 (2004) 488–505]) to present a new general form. The objective is to simultaneously optimize the order quantity, ordering cost, back-order discount and lead time. In addition, we also develop an algorithmic procedure and use the computer software Compaq Visual Fortran V6.0 (inclusive of IMSL) to find the optimal inventory policy. Finally, a numerical example is also given to illustrate the results. [Copyright &y& Elsevier]

Abstract: The well-known recursive least-squares (RLS) algorithms are directly dependent on the recursive estimation method for inversion of the auto-correlation matrix based on the matrix inverse lemma. On the basis of recursive estimation of the augmented cross-correlation matrix and the well-known power iteration, this paper establishes a recursive total instrumental-variable (RTIV) algorithm for tracking the total least-squares (TLS) solution of the normal equations in the over-determined instrumental-variable methods. Under the condition that the recursive estimation of the augmented cross-correlation matrix is asymptotically convergent, we show that the weight vector in the RTIV algorithm converges to the direction parallel to the singular vector associated with the smallest singular value of the augmented cross-correlation matrix. When the algorithm is applied in a parameter estimation problem, the converging weight vector corresponds to the TLS solution of the over-determined normal equations. Since the estimated parameters are optimal in the TLS sense, in the case where noise exists in both the input and output of the system or with the short sampling data, its noise rejection capability is superior to that of least-squares-based algorithms. The applicability and performance of the RTIV algorithm are demonstrated by computer simulations for adaptive IIR filtering and harmonic retrieval. [Copyright &y& Elsevier]

The DTD of a set of XML documents may change due to many reasons such as changes to the real-world events, changes to the user’s requirements, and mistakes in the initial design. In this paper, we present a novel algorithm called DTD-Diff to detect the changes to DTDs that defines the structure of a set of XML documents. Such change detection tool can be useful in several ways such as maintenance of XML documents, incremental maintenance of relational schema for storing XML data, and XML schema integration. We compare DTD-Diff with existing XML change detection approaches and show that converting DTD to XML schema (XSD) (which is in XML document format) and detecting the changes using existing XML change detection algorithms is not a feasible option. Our experimental results show that DTD-Diff is 5–325 times faster than X-Diff when it detects the changes to the XSD files. Compared to XyDiff, DTD-Diff is up to 38 times faster. We also study the result quality of detected deltas. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematical analysis and computer algebra, a reliable algorithm of finite difference method for solving singular perturbation problems was established, a new matlab procedure ehssp was implemented, too. Several linear and non-linear problems are presented to illustrate the implementation of the program. [Copyright &y& Elsevier]

In this paper, uncertainties in the retrieval of satellite surface chlorophyll concentrations in the Mediterranean Sea have been evaluated using both regional and global ocean colour algorithms. The rationale for this effort was to define the most suitable ocean colour algorithm for the reprocessing of the entire SeaWiFS archive over the Mediterranean region where standard algorithms were demonstrated to be inappropriate. Using a large dataset of coincident in situ chlorophyll and optical measurements, covering most of the trophic regimes of the basin, we validated two existing regional algorithms [Bricaud, A. , E. Bosc, and D. Antoine, 2002. Algal biomass and sea surface temperature in the Mediterranean Basin — Intercomparison of data from various satellite sensors, and implications for primary production estimates. Remote Sensing of Environment, 81(2–3), 163–178. ; D''Ortenzio, F. , S. Marullo, M. Ragni, M. R. D''Alcala and R. Santoleri, 2002. Validation of empirical SeaWiFS algorithms for chlorophyll-alpha retrieval in the Mediterranean Sea — A case study for oligotrophic seas. Remote Sensing of Environment, 82(1), 79–94. ] and the global algorithm OC4v4 used for standard NASA SeaWiFS products. The results of our analysis confirmed that the OC4v4 performs worse than the two existing regional algorithms. Nonetheless, these two regional algorithms do show uncertainties dependent on chlorophyll values. Then, we introduced a better tuned algorithm, the MedOC4. Using an independent set of in situ chlorophyll data, we quantified the uncertainties in SeaWiFS chlorophyll estimates using the existing and new regional algorithms. The results confirmed that MedOC4 is the best algorithm matching the requirement of unbiased satellite chlorophyll estimates and improving the percentage of the satellite uncertainty, and that the NASA standard chlorophyll products are affected by an uncertainty of the order of 100%. Moreover, the analysis suggests that the poor quality of the SeaWiFS chlorophyll in the Mediterranean is not due to the atmospheric correction term but to peculiarities in the optical properties of the water column. Finally the observed discrepancy between the global and the regional bio-optical algorithms has been discussed analysing the differences between the two in situ datasets used for tuning the algorithms (SeaBASS versus ours). The main results are that methodological differences in the two datasets cannot play a major role and the inherent bio-optical properties of the basin can explain the observed discrepancy. In particular the oligotrophic water of the Mediterranean Sea is less blue (30%) and greener (15%) than the global ocean. [Copyright &y& Elsevier]

Abstract: Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program. [Copyright &y& Elsevier]

Abstract: For many scientists working with digital topographic data, extracting lineaments or linear features is an important step in structuring and analyzing raw data. A ridge axis, which represents the top a mountain ridge, is one of the most important topographic features used in a wide variety of applications. Algorithms and software for automating the extraction of ridges or ridge axes from DEMs are, however, still not easily available or not widely acceptable. In this paper, we present a user-friendly Visual Basic program that automates the extraction of the ridge axis system from DEM data, based on the profile-recognition and polygon-breaking algorithm (PPA). An important feature of PPA is that it takes a global approach, as opposed to the local neighborhood operators used in many other algorithms. Each segment detected by PPA considers not only relations with contiguous neighboring grid points, but also strives to preserve the continuity of the global trend. This is an attempt to simulate human operators, who always factor in the overall trend of the lineament before delineating its local parts. PPA starts by connecting all points in a neighborhood that can possibly lie on the ridge axis, thus forming a belt of polygons in the first step. Next, a polygon breaking process eliminates unwanted segments according to the assumption that a ridge segment cannot be the side of any closed polygon, and that the result should be a purely dendritic line pattern. Finally, a branch-reduction process is executed to eliminate all parallel false ridges that remained due to the conservative approach taken in the first step. Results indicate that PPA is reasonably successful in picking out ridges that would have been identified manually by experts. In addition to providing a detailed user interface for executing PPA, several modifications were made to significantly improve the computational efficiency of PPA, as compared to the original version published in 1998. The source codes are provided for free download on the website listed above. [Copyright &y& Elsevier]

Abstract: This paper considers some permutation flow shop scheduling problems with a learning effect on no-idle dominant machines. The objective is to minimize maximum completion time. This objective is considered under following dominant machines constraint: idm, ddm, idm–ddm and ddm–idm. We present a polynomial-time solution algorithm for each of the above cases. [Copyright &y& Elsevier]

Abstract: A semiretract of a free monoid is an intersection of a family of retracts of and it is a free submonoid. In the paper we propose an algorithmic approach to the problem of finding the base (code) of a semiretract. [Copyright &y& Elsevier]

Abstract: A stress–strain constitutive equation of non-linear combined hardening rule has been proposed in this paper according to non-linear kinematic hardening theory of Lemaitre and Chaboche and Barlat89’s yielding function. The algorithm of elastic predicting, plastic correcting and radial returning is applied to calculate the stress increment. Taking a benchmark of NUMISHEET’93 2-D draw bending problem as an example, the effects of different hardening rules and yielding functions are investigated. Comparison with NUMISHEET’93 experiment data indicates that the isotropic hardening rule over-predicts springback since the predicted stress after forming is relatively larger, while the predicted springback by non-linear combined hardening rule coincides well with experimental data. In addition to that, the study indicates that Barlat89’s and Hill48’s yielding functions describe the practical material behavior better than Mise’s yielding function, and the predicted results by Barlat89’s and Hill48’s yielding criterion are very closer to experiment data. [Copyright &y& Elsevier]

Abstract: In this paper, we first show a DNA representation of a ternary number with digit set {−1,0,1}, which features its address and each bit position. Based on this DNA representation, operations for value assigning and bit position shifting are proposed. The algorithm of DNA computing for adding two ternary integers is presented. The algorithm works in O(m) steps for adding two ternary integers of m bits. [Copyright &y& Elsevier]

Abstract: In this paper we study the higher secant varieties of Grassmann varieties in relation to the functional Waring’s problem for alternating tensors and to the Alexander–Hirschowitz theorem. We show how to identify defective higher secant varieties of Grassmannians using a probabilistic method involving Terracini’s lemma, and we describe an algorithm which can compute, by numerical methods, dim (S s G(k, n)) for n ⩽14. Our main result is that, except for Grassmannians of lines, if n ⩽14 and (if n =14 we have studied the case k ⩽5) there are only the four known defective cases: S 2 G(2,6), S 2 G(3,7), S 3 G(3,7) and S 3 G(2,8). [Copyright &y& Elsevier]

Abstract: A n × n real matrix P is said to be a real generalized reflection matrix if P T = P and P 2 = I. A n × n real matrix X is said to be a reflexive matrix with respect to the generalized reflection matrix P if X = PXP. In this paper, the concept of gradient matrix (∇F(X)) is presented and an algorithm is constructed to solve the reflexive with respect to the generalized reflection matrix P solution of the minimum Frobenius norm residual problem:. By this algorithm, for any initial reflexive matrix X 1, a solution X ∗ can be obtained within finite iteration steps in the absence of roundoff errors, and the solution X ∗ with least-norm can be obtained by choosing a special kind of initial reflexive matrix. In addition, in the solution set of above problem, the unique optimal approximation solution to a given matrix X 0 in Frobenius norm can be obtained by finding the least-norm reflexive solution of the new minimum residual problem: , where , . Given numerical examples show that the iterative method is quite efficient. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce and study completely generalized multivalued nonlinear co-quasi-variational-like inclusions. By using J η-proximal mapping [1], we propose an iterative algorithm for computing the approximate solutions of completely generalized multivalued nonlinear co-quasi-variational-like inclusions problem. We prove that approximate solutions obtained by the proposed algorithm converge to the exact solutions of completely generalized multivalued nonlinear co-quasi-variational-like inclusions problem. Some special cases are also discussed. [Copyright &y& Elsevier]

Abstract: In this paper we equate the problem of predicting the loop 3D structure in the comparative modeling to a problem of finding the maximal clique with the best weight. Each possible conformation of a residue in a loop sequence is represented as a node in a graph. Edges are then drawn between pairs of nodes that are consistent with each other. Edge and nodes are weighted according to some fixed criteria. Once the entire graph is constructed, all the maximal sets of cliques are found using an algorithm of artificial neural network models. The cliques with the best weights represent the optimal conformation of the region of loop sequence. [Copyright &y& Elsevier]

Abstract: This paper presents a numerical formulation for frictional contact problems associated with pile penetration. The frictional contact at the soil–pile interface is formulated using the theory of hardening/softening plasticity, so that advanced models for the interface can be dealt with. A smooth discretisation of the pile surface is proposed using Bézier polynomials. An automatic load stepping scheme is proposed, which features an error control algorithm and automatic subincrementation of the load increments. The numerical algorithms are then used to analyse the installation process of pushed-in axial piles. It is shown that the smooth discretisation of the pile surface is effective in reducing the oscillation in the predicted pile resistances and the automatic load stepping scheme outperforms the classical Newton–Raphson scheme for this type of problem. [Copyright &y& Elsevier]

Abstract: The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number of a graph G is the minimum cardinality of a power dominating set of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for solving the power domination problem in block graphs. As an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs. [Copyright &y& Elsevier]

Abstract: Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer , it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15–29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61–72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977–979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147–157] and it has been open for a long time whether this problem can be solved in time. In this paper, we will provide a simple and efficient -time algorithm for solving this problem. [Copyright &y& Elsevier]

Abstract: Firstly, the twisted block decompositions of the block tridiagonal matrices are presented. According to the special structure of the decomposition, the formulae of computing the block elements of each column of the inverse matrices are obtained. Then an algorithm of inverting the block tridiagonal matrices has been established. The explicit expressions of the block elements of the inverse matrices are also presented. At last, for the algorithm in this paper and some existed algorithms for the inverse matrices, the calculating complexity and the calculating time have been compared. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce a new approach to line drawing that attempts to maintain a uniform packing density of horizontal segments to diagonal segments throughout the line. While the conventional line drawing algorithms perform linear time computations to find the location of the pixels, our algorithm takes logarithmic time. Also, experimental results show that the quality of line is acceptable and comparable to the well-known Bresenham''s line-drawing algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we present a simple and effective feedback algorithm for endless polarization control that uses two wave plates with rotating axes and variable birefringence. We derive the error function and introduce the principle of the feedback control algorithm, and then we prove its feasibility with simulations. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematical analysis and computer algebra, a reliable algorithm for solving the second kind of Volterra integral equation is established, and a new Maple procedure voltproc is established, too. In particular, the algorithm can provide the exact solution of the second kind of Volterra integral equation by the methods of Neumann-series and mathematical induction, i.e., the algorithm also can computing the nth term by finite terms of the iterative kernel. Some examples are presented to illustrate the efficiency and accuracy of the algorithm. This will be useful for the integral equation solving and mathematical theorems automatic proving. [Copyright &y& Elsevier]

Abstract: The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions. [Copyright &y& Elsevier]

Abstract: In this paper, we present a linear time algorithm to remove winding of a simple polygon P with respect to a given point q inside P. The algorithm removes winding by locating a subset of Jordan sequence that is in the proper order and uses only one stack. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate various properties and problems associated with the maximum weight triangulation of a point set in the plane. We prove that the weight of a maximum weight triangulation of any planar point set with diameter D is bounded above by , where ɛ is any constant and n is the number of points in the set. If we use the so-called spoke-scan algorithm to find a triangulation of the point set, we obtain an approximation ratio of 4.238. Furthermore, if the point set forms a semi-circled convex polygon, then its maximum weight triangulation can be found in time. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of integral equation and computer algebra, a reliable algorithm for solving the Volterra integral equation is established, and a new Maple algorithm mainproc is established, too. Some examples are presented to illustrate the implementations of the algorithm. The results of the examples indicate that the algorithm of Taylor polynomial method is simple and effective, and can provide an accuracy approximate solution or exact solution of the Volterra integral equation and integro-differential equation. This will be useful for solving a system of integral equation or integro-differential equation. [Copyright &y& Elsevier]

Abstract: Integral equation has been one of principal tool of various areas of applied mathematics, physics and engineering. In this paper, by using the theories and methods of mathematical analysis and computer algebra, a reliable algorithm for solving the second kind of Fredholm integral equation is established, and a mechanical Maple algorithm fredholmproc is established, too. The algorithm can provide the continuous solution of the second kind of Fredholm integral equation. Ten examples are presented to illustrate the efficiency and accuracy of the algorithm. This will be useful for solving the integral equation. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematics analysis, ordinary differential equation and computer algebra, a reliable algorithm for solving ordinary differential equation (ODE) was established, and a new Maple procedure mechodeproc was established, too. The results of the examples indicated that the procedure mechodeproc based on Taylor polynomial method was simple and effective, and could provide an accuracy approximate solution or exact solution of the ordinary differential equation. This would be useful for solving differential equation. [Copyright &y& Elsevier]

Abstract: In this paper, by using theories of stochastic process and computer algebra, a reliable algorithm for computing the high-order transition probability matrix of finite Markov chain is established, a new mechanical procedure markovproc is established, too. The procedure markovproc give not only the exact expression of the Markov chains, but also the limiting probability. Some examples are presented to illustrate the implementation of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematics analysis and computer algebra, a reliable algorithm for solving high-order nonlinear Volterra–Fredholm integro-differential equations was established, and a new Maple procedure voltfredproc was established too. The results of the examples indicated that the procedure voltfredproc of Taylor polynomial method is simple and effective, and could provide an accuracy approximate solution or exact solution of the high-order nonlinear Volterra–Fredholm integro-differential equation. This would be useful for solving integro-differential equation, integral equations and ordinary differential equation. [Copyright &y& Elsevier]

Abstract: The present paper discusses the algorithm and mechanization to the Cauchy problem of parabolic equation. The author uses the initial data to construct the solutions that satisfy the initial condition and obtain a brief algorithm to this problem. Thereafter, the algorithm is used in Maple to solve this Cauchy problem automatically. [Copyright &y& Elsevier]

Abstract: One of the main problems dealing with iterative methods for solving polynomial systemsis the initialization of the iteration. This paper provides an algorithm to initialize the search of solutions of polynomial systems. [Copyright &y& Elsevier]

Abstract: This paper presents DNA algorithms for five relational algebra database operations, selection, projection, union, set difference, and Cartesian product on so-called DNA databases. A DNA database is a database where data records are encoded as DNA strands. The five operations mentioned before are fundamental in the field of databases and perform most of the data retrieval operations on current databases. [Copyright &y& Elsevier]

Abstract: In this paper a new hierarchical extension of the algorithm for robot path planning is introduced. The hierarchical algorithm uses a down-top strategy and a set of precalculated paths (materialization of path costs) in order to improve performance. This on-line path planning algorithm allows optimality and specially lower computational time. H-Graphs (hierarchical graphs) are modified and adapted to support on-line path planning with materialization of costs and multiple hierarchical levels. Traditional on-line robot path planning focused in horizontal spaces is also extended to vertical and interbuilding spaces. Some experimental results are showed and compared to other path planning algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the random generalized nonlinear mixed variational inclusions for random fuzzy mappings and define an iterative algorithm for finding the approximate solutions of this class of variational inclusions. We also establish that the approximate solutions obtained by our algorithm converge to the exact solution of the random generalized nonlinear mixed variational inclusions for random fuzzy mappings. [Copyright &y& Elsevier]

Abstract: The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink. [Copyright &y& Elsevier]