二机器流水作业排序问题全部最优解的结构

排序问题F2||Cmax,Johnson条件只是最优解的充分条件，不是必要的．本文绘出一个充分必要条件，由此得到生成全部最优解的算法．主要理论是基于一种序论方法．     

关于图与补图的带宽的一个简单证明

关于图与补图的带宽,P.Z.Chinn,F.R.K.Chung,P.Erd?s和R.L.Graham证明了B(G)+B(G)≥n-2.本文给出一个简单证明.     

六角系统的一类极值问题

本文引进六角系统的两个基本参数——宽度和直径,并讨论有关的极值、极图结构及计数问题。对极值问题已得到完满结果。对极图构造及计数问题尚有一些情形未能得出好的结果。     

限位排序的若干结果

In this paper,we first consider the position restriction scheduling problems on a single machine.The problems have been solved in certain special cases,especially for those obtained by restricting the processing time pj=1.We introduce the bipartite matching algorithm to provide some polynomial-time algorithms to solve them.Then we further consider a problem on unrelated processors.     

关于带宽极值问题的一些结果

本文研究的问题是确定f(p,B）的值，也就是给定顶点数p和带宽B，求满足最大度不超过B的连通图的最小边数，本文给出了一些f(p,B）的值及相应极图。     

直径不超过4的树的割宽

§ 1　IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see [2 ] ) .We shall follow the graph-theoretic terminology and notation of [1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…     

关于连贯的计数问题

大家知道,两类元素连贯的理论在质量控制中、两种处理的效果比较中都得到了广泛的应用.利用连贯的理论,还可以发现微小的系统误差.在铁路运输、多种处理的效果比较等实际问题中,还遇到了多类元素的连贯问题.如利用多类元素连贯的理论,可以很好地解决过去中外文献中尚未见到的铁路运输中“组号和平均解体钩数”关系问题.所以,多类元素连贯理论的研究有其实际的和理论的意义.     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．