Search

A subsetFof vertices of a graphGis called a vertex coverPkset if every path of orderkinGcontains at least one vertex fromF. Denote by ψk(G) the minimum cardinality of a vertex coverPkset inG. The vertex coverPk(VCPk) problem is to find a minimum vertex coverPkset. It is easy to see that theVCP2problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to theVCP4problem in cubic graphs. The paper proves that theVCP4problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on ψ4(G) for cubic graphs and propose a 2-approximation algorithm for theVCP4problem in cubic graphs. [ABSTRACT FROM PUBLISHER]

In this paper, applying a novel second-order numerical approximation formula for the Riesz derivative and Crank–Nicolson technique for the temporal derivative, a numerical algorithm is constructed for the two-dimensional spatial fractional diffusion equation with convergence order, whereτ,andare the temporal and spatial step sizes, respectively. It is proved that the proposed algorithm is unconditionally stable and convergent by using the energy method. Meanwhile, by adding the high-order perturbation items for the above numerical scheme, an alternating direction implicit difference scheme is also constructed. Finally, some numerical results are presented to demonstrate the validity of theoretical analysis and show the accuracy and effectiveness of the method described herein. [ABSTRACT FROM AUTHOR]

Roughk-means clustering algorithm and its extensions are introduced and successfully applied to real-life data where clusters do not necessarily have crisp boundaries. Experiments with the roughk-means clustering algorithm have shown that it provides a reasonable set of lower and upper bounds for a given dataset. However, the same weight was used for all the data objects in a lower or upper approximate set when computing the new centre for each cluster while the different impacts of the objects in a same approximation were ignored. An improved roughk-means clustering based on weighted distance measure with Gaussian function is proposed in this paper. The validity of this algorithm is demonstrated by simulation and experimental analysis. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new Galerkin spectral element method for one-dimensional fourth-order boundary value problems. We first introduce some quasi-orthogonal approximations in one dimension, and establish a series of results on these approximations, which serve as powerful tools in the spectral element method. By applying these results to the fourth-order boundary value problems, we establish sharpanderror bounds of the Galerkin spectral element method. The efficient algorithm is implemented in detail. Numerical results demonstrate its high accuracy, and confirm the theoretical analysis well. [ABSTRACT FROM AUTHOR]

In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graphG, each pair of vertices are joined by an edge with a probabilityp, wherepis a constant between 0 and 1. We show that a maximum independent set in a random graph that containsnvertices can be computed in expected computation time. In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph innvertices can be approximated within a ratio ofin expected polynomial time. [ABSTRACT FROM AUTHOR]

In dynamical systems saddle points partition the domain into basins of attractions of the remaining locally stable equilibria. This situation is rather common especially in population dynamics models, like prey–predator or competition systems. Focusing on squirrels population models with niche, in this paper we design algorithms for the detection and the refinement of points lying on the separatrix manifold partitioning the phase space. We consider both the two populations and the three populations cases. To reconstruct the separatrix curve and surface, we apply the Partition of Unity method, which makes use of Wendland's functions as local approximants. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of capacitated covering with unit balls. In this problem, a set of weighted points in a metric spaceis given, and we want to cover them with a minimum number of the unit balls of that metric space provided that the total weight assigned to each unit ball is at most one. The problem is NP-hard as it generalizes the covering-with-unit-balls problem. We consider the problem in two cases: (1) the weight of each point can be split among several unit balls and (2) the unsplittable case. In the latter case, the problem is a generalization of the bin-packing problem even when, and thus it is not approximable under 1.5, unless P=NP. We design a polynomial-time approximation scheme (PTAS) for the splittable case whenis a fixed constant andis anmetric. This also results in a PTAS for the unsplittable case when all the points have the same weight. We also analyse several natural algorithms for this problem and prove that they achieve constant approximation factors. [ABSTRACT FROM AUTHOR]

In this paper, we propose a generalized Laguerre spectral method for Fisher's-type equation with inhomogeneous boundary conditions on a semi-infinite interval. By reformulating the equation with suitable functional transform, it is shown that the generalized Laguerre approximations are convergent on a semi-infinite interval with spectral accuracy. An efficient and accurate algorithm based on the generalized Laguerre approximations to the transformed equation is developed and implemented. Numerical results show the efficiency of this approach and coincide well with theoretical analysis. [ABSTRACT FROM PUBLISHER]

This paper focuses on a multistep splitting method for a class of nonlinear viscous equations in two spaces, which uses second-order backward differentiation formula (BDF2) combined with approximation factorization for time integration, and second-order centred difference approximation to second derivatives for spatial discretization. By the discrete energy method, it is shown that this splitting method can attain second-order accuracy in both time and space with respect to the discreteL2- andH1-norms. Moreover, for improving computational efficiency, we introduce a Richardson extrapolation method and obtain extrapolation solution of order four in both time and space. Numerical experiments illustrate the accuracy and performance of our algorithms. [ABSTRACT FROM PUBLISHER]