Determining the number of internal stability of a graph

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.     

High-accuracy quadrature methods for solving boundary integral equations of steady-state anisotropic heat conduction problems with Dirichlet conditions

This paper presents the mechanical quadrature methods (MQMs) for solving the boundary integral equations of steady-state anisotropic heat conduction equation on the smooth domains and polygons, respectively. The costless and high-accurate Sidi–Israeli quadrature formula are applied to deal with the integrals in which the kernels have a logarithmic singularity. Especially, the Sidi transformation is used for the polygon cases in order to obtain a rapid convergence by degrading the singularity at the corners on the boundary. The convergence and stability of the MQMs solution are proved based on Anselone's collective compact theory. In addition, asymptotic error expansion of the MQMs shows that the approximation order is of O(h³), where h is the partition size of the boundary. Finally, numerical examples are tested and results verify the theoretical analysis.     

Improving the Parameterization of Approximate Subdivision Surfaces

We provide a method for improving the parameterization of patching schemes that approximate Catmull‐Clark subdivision surfaces, such that the new parameterization conforms better to that of the original subdivision surface. We create this reparameterization in real‐time using a method that only depends on the topology of the surface and is independent of the surface's geometry. Our method can handle patches with more than one extraordinary vertex and avoids the combinatorial increase in both complexity and storage associated with multiple extraordinary vertices. Moreover, the reparameterization function is easy to implement and fast.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

方案偏好已知的三角模糊数型多属性决策方法

研究决策者对方案偏好已知、属性值以三角模糊数形式给出且属性权重信息不能完全确知的多属性决策问题.提出了基于模糊比例值的决策方法和基于模糊偏差度的决策方法,这两种方法首先建立一个线性规划模型,通过求解该模型获得属性权重;然后,基于三角模糊数两两比较的可能度公式及三角模糊数排序公式,对决策方案进行排序和择优;最后,通过实例验证了方法的可行性和有效性.     

基于分式规划的区间直觉梯形模糊数多属性决策方法

针对属性值为区间梯形直觉模糊且属性权重为区间数的多属性决策问题,提出一种基于分式规划的决策方法.定义了区间梯形直觉模糊数的Hamming距离和Euclidean距离,采用优劣解距离法构建了相对贴近度的非线性分式规划模型,并通过Charnes and Cooper变换转化为线性规划模型求解,得到各方案相对贴近度的区间数,进而提出了决策方法.数值算例分析验证了所提出方法的有效性.     

完全图的点可区别强全染色算法

根据图的点可区别全染色的定义,结合完全图的对称性,提出一种新的点可区别强全染色算法。该算法将需要填充的颜色分为超色数和正常色数2个部分,在得到染色数量和染色次数的前提下,对超色数进行染色以增强算法收敛性。实验结果表明,该算法具有较低的时间复杂度。     

一种新的灰色多属性决策方法

针对模糊群体多属性决策问题,提出一种新的灰色多属性决策方法.该方法依据一般的灰色关联分析方法的基本思路,将灰色关联度和欧氏距离有机结合,构造出一种平均相似度对方案进行评价.平均相似度同时反映了方案与正负理想方案之间的位置和数据曲线的相似性差异,其物理意义更加明确.最后通过算例表明了所提出方法的可行性和有效性.