On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.     

On the spectral radius of H-shape trees

A H-shape is a tree with exactly two of its vertices having maximal degree 3. In this paper, we show that 2≤λ₁ (H)<√ 5, where λ₁ (H) is the spectral radius of H.     

非树调和图的必要条件与非调和图类

使用同余的方法,给出了一般调和图的必要条件;还给出正则图、Euler图、圈的粘接以及圈的并是调和图的必要条件。指出了Euler图中的非调和图类,m个n圈的粘接图中的非调和图类。构造了偶圈的具有同顶点的调和母图。     

Gold码的因子图迭代捕获方法

为降低Gold码的捕获时间与复杂度,提出将基于因子图的迭代m序列捕获算法应用于Gold码捕获. 以全球定位系统(GPS)信号的C/A码为例,首先根据Gold码的生成多项式确定1组具有稀疏结构的校验关系;然后为降低迭代计算的复杂度,提出了不同校验关系顺次校验与混合校验的迭代捕获算法;最后通过仿真研究比较了不同的校验关系和校验方法对迭代捕获算法性能的影响. 仿真结果表明,顺次迭代且迭代次数递减的校验方法最优,该方法能在不损失检测概率的情况下降低Gold码捕获的复杂度,同时降低其捕获时间.     

基于模型的混杂系统中控制器故障诊断方法

为解决混杂系统中控制器故障诊断问题,提出一种混杂系统故障发生在控制器与设备组件之上的新诊断方法,解决了控制器故障检测与诊断问题,并给出解决上述问题的基本诊断算法.实验结果表明,该算法程序简单且效率较好,对于复杂的被诊断对象可以满足实时性.     

超级λ_3-最优二部图的充分条件

图的k-限制边连通度是图的边连通度概念的推广,用它可以更加精确的度量网络的可靠性。通过讨论λ3-最优但非超级λ3-最优二部图的性质得到了二部图超级λ3-最优的充分条件。     

一个特殊图形的边色数

从Petersen图出发,找到一个图形并证明其边色数为7.从说明D.R.Fulkerson在1971年提出的一个猜想是不成立的.在此基础上,还进一步证明了该猜想成立的一些充分条件.     

P部图的Kirchhoff指标下界

连通图G的两个顶点i和j之间的电阻距离rij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值．图G的Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和．得到了n阶p部图G=G（N1,N2,…,Np）（｜Ni｜=ni,i=1,2,…,p）的Kirchhoff指标下界,指出当G为完全p部图时达到下界;并进一步得到,在所有的n阶p部图中,图兰图的Kirchhoff指标最小．     

一些 DNA 图的标号

为了读取DNA序列,Blazewicz等人提出了(α,k)-可标号的有向图的概念,称有向图D是DNA图若D是(4,k)-可标号的.基于此,证明了(α,k)-可标号的有向路和有向圈的充要条件.设T是一棵只有一个入(出)度为0的点的定向树,还证明了T是(α,k)-可标号的有向图的必要条件和T是DNA图的充要条件.     

一类逼近容量LDPC纠删码的二部图构造算法

Tornado码是一类重要的LDPC码． 证明了Heavy-Tail/Poisson度序列可逼近删除信道容量． 提出了Tornado码设计中随机二部图的连边构造算法． 通过分析Heavy-Tail/Poisson度序列的分布,提出了设计Tornado码的一个参数选取原则． 仿真实验证明了这一选取原则的合理性． 随机二部图的连边构造算法及其参数选取原则有助于Tornado码的设计及其工程应用．