Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

基于白化权函数的区间灰数关联度模型

根据区间灰数空间映射思想,引入白化权函数来表征区间灰数的分布信息。定义灰形和灰心分别来描述白化权函数与区间灰数围成的封闭几何图形及其几何重心;定义灰圆和灰径分别来表示以灰心为圆心且与灰形具有相同面积的标准圆及其半径。在此基础上,以灰心序列的横、纵坐标序列为对象,以灰径的离差为权重,依照邓氏关联度原理构造了一个基于白化权函数的区间灰数关联度模型。并针对一种最为典型的白化权函数,具体导出了区间灰数关联度的计算公式。最后,通过一个供应商选择的实例验证了模型的科学性和可行性。基于白化权函数的区间灰数关联度在资源勘探、机器故障诊断、产品品质评价及供应商选择等方面有着广泛的应用前景。     

The Enhanced Double Digest Problem for DNA Physical Mapping

The double digest problem is a common NP-hard approach to constructing physical maps of DNA sequences. This paper presents a new approach called the enhanced double digest problem. Although this new problem is also NP-hard, it can be solved in linear time in certain theoretically interesting cases.