给定部分大小的最大有向割问题的一种近似方法

给出了求解给定部分大小的最大有向割问题的一种新的近似方法,并讨论了它的性能保证.该方法的核心是利用Pipage技术,并结合线性松驰的基本解的特性,为给定部分大小的最大有向割问题设计出了0.5-近似算法.

特殊度条件下有向图的最大有向割

对于整数k,l≥0,用D(k,l)表示一类有向图的集合,这类图的每个顶点要么入度不超过k要么出度不超过l.研究了度条件下有向图中的最大有向割问题,目的是确定图类D(k,l)中有向图的最大有向割包含的弧的条数.对于包含m条弧的有向图,通过分析图的结构,采用数学归纳法,得到(1)若D∈D(2,3)∪D(3,2),则存在至少包含2m/7条弧的有向割;(2)设D∈D(k,k),若存在顶点集的一个二部划分(X,Y),使得X中点的入度与Y中点的出度都不超过k,并且起点在X中终点在Y中的弧的集合的导出图的基础图不含圈,则存在至少包含(1/4+1/(8k+4))m条弧的有向割.

单平面有向无圈图中最小路覆盖问题的算法研究

一个铁路区段在规划时间内的时空网络是一个仅包含一对源与汇的有向无圈平面图。每个列车都可由该网络中的一条有向路表示。本文研究上述网络中的最小路覆盖问题,即至少用多少条有向路可以覆盖图中所有的边。根据单平面有向无圈图的单源单汇和平面性等结构性质,本文给出了上述问题的一个时间复杂度为O(nk)的精确算法,这里n表示图中顶点数、k表示图中最大有向割所包含边的数目。