Z_P群中N维广义正方体上的哈密顿回路

设Z_P={1,2,…,P-1,0},在模P的加法运算下,Z_P是一个群。Z_P上定义n维广义正方体,其顶点集为{(x_1,x_2,…,x_n):x_i∈Z_P.i=1,2,…,n},两个顶点x和y之间有一条棱,当且仅当sum from i=1 to n丨x_i-y_i丨=1 mod(P)。在这个定义下,本文证明了对任意P≥2和n≥2,Z_P中n维广义正方体上存在一个经过所有顶点的哈密顿回路。文中给出了一些例子作为应用。     

Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes. The author is partially supported by NSF CCR-0311174.     

冲突视角下运输订单商业竞争战略研究

运用图模型理论研究冲突视角下中欧班列运营过程中运输订单商业竞争战略,构建“渝新欧”班列运营商、“苏满欧”班列运营商和昆山IT企业之间的商业竞争冲突模型。利用TOPSIS法评估班列的运输效率,确定决策者偏好,通过计算均衡解获得符合各决策者利益的理性对策。借助灵敏度分析研究决策者偏好改变对模型冲突结果的影响。研究表明:在竞争中,运输效率较低的一方可以通过降低价格弥补自身劣势而获得订单;运输效率较高的一方只有通过降价才能获得订单。该研究为班列运营商提供利益冲突中的商业竞争战略,能为顾客企业选择高效合理的运输线路提供有效的战略决策,同时亦能为宏观调控者规范市场、提高市场运输效率提供有效的政策启示。     

Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil

Motivated by a proposal of the local authority for improving the existing healthcare system in the Parana State in Brazil, this article presents an optimization-based model for developing a better system for patients by aggregating various health services offered in the municipalities of Parana into some microregions. The problem is formulated as a multi-objective partitioning of the nodes of an undirected graph (or network) with the municipalities as the nodes and the roads connecting them as the edges of the graph. Maximizing the population homogeneity in the microregions, maximizing the variety of medical procedures offered in the microregions, and minimizing the inter-microregion distances to be traveled by patients are considered as three objective functions of the problem. An integer-coded multi-objective genetic algorithm is adopted as the optimization tool, which yields a significant improvement to the existing healthcare system map of the Parana State. The results obtained may have a strong impact on the healthcare system management in Parana. The model proposed here could be a useful tool to aid the decision-making in health management, as well as for better organization of any healthcare system, including those of other Brazilian States.     

A graph coloring approach for image segmentation

In this paper we develop a segmentation scheme for digital images based upon an iterative binary coloring technique that takes into account changing behavior of adjacent pixels. The output is a hierarchical structure of images which allows a better understanding of complex images. In particular, we propose two algorithms that should be considered as image preprocessing techniques.     

An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem

We present a new Immune Algorithm, IMMALG, that incorporates a Stochastic Aging operator and a simple local search procedure to improve the overall performances in tackling the chromatic number problem (CNP) instances. We characterize the algorithm and set its parameters in terms of Kullback Entropy. Experiments will show that the IA we propose is very competitive with the state-of-art evolutionary algorithms.     

Decompositions of λ K v

In a series of 2 papers, Kang, Du and Tian solved the existence problem for G-decomposition of λ K _n when G is any simple graph with 6 vertices and 7 edges, except when G is the graph T=K ₄∪K ₂. Notice that a T-decomposition can be considered to be a Pairwise Balanced Design in which each block of size 4 has been matched to a block of size 2. In this paper we remove this exception for all λ≥2. The case when λ=1 is also addressed. This paper is written in honor of Frank Hwang on the occasion of his 65th birthday.     

On edge orienting methods for graph coloring

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.     

略论《山海经图》的流传情况

现存的《山海经》是《山海经图》的释读文字 ,所以要研究《山海经》还必须对《山海经图》的有关情况进行考证。《山海经图》亡佚的时间 ,大致可推定在汉宣帝至汉成帝之间     

计算机辅助机构运动分析图解法

借助于 Auoto CAD强有力的绘图功能及其内嵌式Autolisp语言,准确、迅速、直观、简便地解决机构运动分析中的问题。