Hamming距离下瓶颈约束最小支撑树反问题

讨论Hamming距离下瓶颈型约束最小支撑树反问题,给定的一个支撑树,修改给定网络边上的费用,使给定的支撑树成为最小支撑树且支撵树中边费用最大值不超过给定的常数,用瓶颈Ham-ming距离来衡量修改的权值,并给出瓶颈Hamming距离下的约束最小支撑树反问题定理的证明.     

关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

哈明距离下费用受限制约束最小支撑树反问题

讨论了瓶颈型哈明距离下费用受限制的约束最小支撑树反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型哈明距离来衡量修改的费用,且修改的总费用不超过给定的上界.利用转化的思想,给出瓶颈型哈明距离下费用受限制的约束最小支撑树反问题的多项式算法及证明.     

特定材料构建支撑树问题的近似算法研究

结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w, c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。     

一类网络系统中的容量扩张问题

考虑一种网络系统中的容量扩张问题：给定网络N（V,E,C^-）,如何对容量向量C^-进行扩张,在假设的每条过的扩张费用（包括固定费用与成本费用）的条件下,使得网络中最大容量树的容量尽可能提高,同时总的扩张费用不超过给定的预算D。讨论了此类问题的特性,并给出了解决问题的一个强多项式算法。     

Hansen和Mélot的一个定理的修改证明

对于给定阶数和悬挂点个数的化学树,P.Hansen等求出了其最小和最大Randi＇c指数,并指出了具有最小和最大Randi＇c指数的化学树的特征,但其证明中出现了一个严重的错误.本研究给出了它的一个正确的证明,通过对这类化学树T恰当地添加悬挂边或者进行剖分,得到一个新的化学树T′,然后利用R（T′）-R（T）的最小值求出R（T）的最小值.     

基于l_1、l_2范数度量的单位时间平行机加权总完工时间的逆调度问题(英文)

考虑了两种范数(l1和l2)度量下,单位时间的平行机上加权总完工时间调度问题的逆问题.对于已经给定的加工工序,在不同范数l1和l2下,通过最小限度地调整工件的权值,使得这一给定的加工工序成为最优,并且工件权值的调整不会增加原有的目标函数值.     

稀疏图上有效的MST多边更新并行算法

ＭＳＴ（最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ之略）多边更新（ｕｐｄａｔｉｎｇ）问题定义如下：给定一个赋权图Ｇ（Ｖ,Ｅ）和Ｇ的一棵最小生成树Ｔ（Ｖ,ＥＴ）,其中｜Ｖ｜＝ｎ,ＥＴ是树边集合,（１）给Ｇ添加Ｋ条新边,或者（２）在图Ｇ上改变Ｋ条边的权后重新为Ｇ寻找一棵最小生成树,１≤Ｋ＜ｎ．本文基于ＳＩＭＤＣＲＥＷＰＲＡＭ共享存贮模型,运用“进－退”策略,并把这一特殊手段与已有的平行算法组合起来,为一类稀疏图（｜Ｅ-ＥＴ｜＝Ｏ（Ｋ））找到了一种有效的ＭＳＴ多边更新算法．该算法需要Ｏ（ｌｏｇｎｌｏｇＫ）时间和Ｏ（ｍａｘ｛ｎ,ｕＫ／ｌｏｇｎｌｏｇＫ｝）处理机．     

平行机上单位加工时间加权总完工时间排序问题的反问题

在给定工序下,排序问题的反问题研究目标是对于预先给定的加工任务,要求确定加工时间或者工件权重的最小调整值,使得给定的工件排序最优。本文研究了平行机上单位加工时间的加权总完工时间排序问题的反问题,即对于给定的加工工序,在不同范数下,通过最小限度调整工件的权值,实现给定加工工序最优,同时满足调整权值后,目标函数值不超过原来的值。     

截断切割问题的优化准则

截断切割是某些工业部门采用的加工方式。针对水平切割与垂直切割费用不同,先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时需要另加调整刀具费用e等问题,给出了以加工费用为目标函数的优化模型,对给定的一组数值得出了最优解。     

交通网络k-短路径与最小支撑树问题

为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

恰有一公共点的双圈图的邻接矩阵的奇异性

恰有一公共点的双圈图的邻接矩阵是奇异的当且仅当G满足：G有完美匹配，c1与c2中一个是4m圈，另一个是偶圈，4m圈上不挂出奇数阶树；G有完美匹配，G-V（c1）-V（c2）含完美匹配，G-V（c1）或G—V（c2）含完美匹配，且含有4m圈；G无完美匹配，G—V（c1）和G—V（c2）均含有完美匹配，且G中含有4k1＋3和4e1＋1（k1，e1∈N）阶图；G，G—V（c1）和G—V（c2）都不含完美匹配恰有一公共点的双圈图的邻接矩阵的行列式的最大值是4．     

开半圆的配置中边的权

在S^1上n个开半圆的简单配置中，顶点或边的权是指包含这的半圆个数，vk,ek分别表示权为k的顶点数和边数，向量v＝（v0,v1，…vn-1）称为配置的v－向量，e＝（e0,e1,…,en）称为配置的e－向量，讨论了非负整数(n＋1）－组数且（e0,e1,…,en）是S^1上n个半圆的配置的边的频率向量的充分必要条件。     

可拆分树的边魔幻全标号性

已知图可以作为无标度网络研究的模型,如小世界网络、层次网络和自相似网络等。研究了树的可拆分和重新组合下的边魔幻全标号性。总可以连接集有序优美树T的某一对不相邻顶点,然后删去一个圈上的一条边,得到一棵具有边魔幻全标号的树。进一步,对满足|T||M|的树M和树T进行拆分和重新组合,进行有限次减圈运算后,得到具有超级边魔幻全标号树。     

3连通图的可去边的分布

e是3连通图G的一条边,如果G-e是某个3连通图的剖分,则称e是G的可去边。研究了3连通图的去边的分布规律,得到：（1）是阶至少为6的3连通图G中的一个圈,如果C上不存在3个连续的3度点,那么C上至少有两条可去边。（2）设T是阶至少为5的连通图G的一棵生成树,如果G中至多存在一个极大半轮,那么T上至少有一条可去边。由此可得：阶至少为5的3连通3正则图的生成树上至少有一条可去边。     

带线性惩罚的次模边点控制集问题的近似算法

考虑带线性惩罚的次模边点控制集问题，给定一个无向图G=(V,E),且V中每个顶点都有一个非负惩罚，E的每个边子集都有一个非负权值.称e={u,v}∈E为边点控制顶点w,如果w∈N[u]∪N[v],这里N[u],N[v]分别为顶点u,v的闭邻域.带线性惩罚的次模边点控制集问题的目标是寻找一个边子集D,使得D的权值与未被D边点控制的顶点的惩罚费用之和最小.利用原始对偶技巧给出此问题的一个k-近似算法，其中k=max_v∈V|N[v]|.     

边-超欧拉图的一个度数和条件

图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e．给出了边-超欧拉图的一个度数和条件,即：设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d（u）＋d（v）≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G（G关于e的剖分图）可以被收缩成K2.3或K2.5．     

网络中支撑树的边扩容问题

受多种网络改进模型的启发,作者研究了网络中支撑树的边扩容问题(GECAT).证明了GECAT问题和限制性最小支撑树问题是多项式等价的,从而说明GECAT是NP-难的.由GECAT问题到限制性最小支撑树问题的等价归约构造方式,得到一个多项式时间近似方法(PTAS).接下来,对GECAT问题的2种特殊形式做了研究并分别给出了强多项式时间算法:支撑树上需扩容边的数目最少问题和最小支撑树所需的扩容费用最少问题.对于前者,采用了T-交换算法,而后者则采用了字典序法.     

基于范数下的反瓶颈Steiner树问题

讨论了在l1范数下的反瓶颈Steiner树问题.对于给定的一个可行解,修改带限制的边权使其成为瓶颈Steiner树问题的最优解,并且在l1范数下边权的修改费用最小.讨论了最优目标值的范围,在此基础上给出了一个求解反瓶颈Steiner问题的多项式时间算法.     

约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.