Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

Betweenness parameterized above tight lower bound

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above its tight lower bound, which is stated as follows. For a set V of variables and set C of constraints “vi is between vj and vk”, decide whether there is a bijection from V to the set {1,…,|V|} satisfying at least |C|/3+κ of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph “Invitation to Fixed-Parameter Algorithms”. The betweenness problem is of interest in molecular biology. An approach developed in this paper can be used to determine parameterized complexity of a number of other optimization problems on permutations parameterized above or below tight bounds.     

A new mathematical programming approach to multi-group classification problems

In this paper we introduce a goal programming formulation for the multi-group classification problem. Although a great number of mathematical programming models for two-group classification problems have been proposed in the literature, there are few mathematical programming models for multi-group classification problems. Newly proposed multi-group mathematical programming model is compared with other conventional multi-group methods by using different real data sets taken from the literature and simulation data. A comparative analysis on the real data sets and simulation data shows that our goal programming formulation may suggest efficient alternative to traditional statistical methods and mathematical programming formulations for the multi-group classification problem.     

A heuristic approach for packing identical rectangles in convex regions

In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme, in which the key step is the perturbation move. Different perturbation moves, both combinatorial and continuous ones, are proposed and compared through extensive computational experiments on a set of test instances. The overall results are quite encouraging.     

基于简单特征值问题的修正GEPSVM

针对GEPSVM可能存在奇异性问题,提出一个改进的GEPSVM算法——SMGEPSVM。基于简单特征值问题,得到2个非平行过原点的超平面。与GEPSVM相比,SMGEPSVM不仅可以求解XOR问题,还可求解简单特征值问题,避免GEPSVM奇异性问题,测试精度好于GEPSVM,学习速度更快,其计算结果在人工数据集与UCI上得到了验证。     

高职《计算机文化基础》教学的困惑与对策

社会已经进入了信息化的时代,计算机技术在社会的发展中起着重要的作用。因此,个人的计算机综合素质也应该相应提高,大学生更是应该如此。高职院校中的一门基础课程就是《计算机文化基础》,这门课对于大学生计算机素质的提高有着积极的作用。下面,笔者对这门课目前的教学现状以及特点进行分析,在此基础上提出一些意见和措施。     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating - a type of non-random mating in which individuals are chosen according to their similarities - may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.     

Necessary optimality conditions for fuzzy variational problems

The main aims of this study are to derive the fuzzy Euler-Lagrange conditions for both fuzzy unconstrained and constrained variational problems based on the concepts of differentiability and integrability of a fuzzy mapping that may be parameterized by the left and right-hand functions of its α-level sets.