几类特殊图中的最小最大多路割

给定边具有正权的无向图,并指定若干个称为终端的顶点,最小最大多路割问题是要得到所有顶点的一个聚类,要求每个子类恰好包含一个终端,并使得所有子类的最大费用最小。子类的费用定义为该子类边界上所有边的权之和。最小最大多路割问题源于对等网络中的数据放置,是传统多路割问题的一个变形。当给定无向图是树图时,这一问题已经是强NP难解的。对于链图和环图,给出了线性时间的精确算法,该算法同时也使得所有子类的总费用最小。对于树图和限制树宽图,给出了(2-1/2k2)-近似算法,k表示终端的数目。     

外1-平面图的均匀边染色

图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

外1-平面图的均匀点荫度

图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。     

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。     

带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).     

基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形予图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(χ)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(х)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

顶点覆盖问题线性内核算法

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).     

欧式平面上瓶颈Steiner树问题的一个近似算法

近些年来，Steiner树问题在理论和应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面，该问题占有一定的中心地位。给定赋权连通图G=(V，E，W)及顶点子集S包含V(S中顶点称为terminals)，传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点，该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时，传统的Steiner树问题仍然是MAX—SNP Hard。     

Approximation Algorithms for <Emphasis Type="Italic">k</Emphasis>-hurdle Problems

The polynomial-time solvable k-hurdle problem is a natural generalization of the classical s-t minimum cut problem where we must select a minimum-cost subset S of the edges of a graph such that |p∩S|≥k for every s-t path p. In this paper, we describe a set of approximation algorithms for “k-hurdle” variants of the NP-hard multiway cut and multicut problems. For the k-hurdle multiway cut problem with r terminals, we give two results, the first being a pseudo-approximation algorithm that outputs a (k−1)-hurdle solution whose cost is at most that of an optimal solution for k hurdles. Secondly, we provide a 2(1-\frac1r)2(1-\frac{1}{r})-approximation algorithm based on rounding the solution of a linear program, for which we give a simple randomized half-integrality proof that works for both edge and vertex k-hurdle multiway cuts that generalizes the half-integrality results of Garg et al. for the vertex multiway cut problem. We also describe an approximation-preserving reduction from vertex cover as evidence that it may be difficult to achieve a better approximation ratio than 2(1-\frac1r)2(1-\frac{1}{r}). For the k-hurdle multicut problem in an n-vertex graph, we provide an algorithm that, for any constant ε>0, outputs a ⌈(1−ε)k⌉-hurdle solution of cost at most O(log n) times that of an optimal k-hurdle solution, and we obtain a 2-approximation algorithm for trees.     

Using graph coloring in an algebraic compiler

An algebraic compiler allows incremental development of the source program and builds its target image by composing the target images of the program components. In this paper we describe the general structure of an algebraic compiler focusing on compositional code generation. We show that the mathematical model for register management by an algebraic compiler is a graph coloring problem in which an optimally colored graph is obtained by composing optimally colored subgraphs. More precisely, we define the clique-composition of graphs and as the graph obtained by joining all the vertices in a clique in with all the vertices in a clique in and show that optimal register management by an algebraic compiler is achieved by performing clique-composition operations. Thus, an algebraic compiler provides automatically adequate clique separation of the global register management graph. We present a linear-time algorithm that takes as input optimally colored graphs and and constructs an optimal coloring of any clique-composition of and . Motivated by the operation of clique-composition, we define the class of clique-composable graphs as those graphs that can be iteratively built from single vertices using the clique-composition operation. We show that the class of clique-composable graphs coincides with the well-known class of chordal graphs. Received: 11 May 1995 / 30 November 1995     

Dynamic monopolies and feedback vertex sets in hexagonal grids

In a majority conversion process, the vertices of a graph can be in one of the two states, colored or uncolored, and these states are dynamically updated so that a vertex becomes colored at a certain time period if at least half of its neighbors were in the colored state in the previous time period. A dynamic monopoly is a set of vertices in a graph that when initially colored will eventually cause all vertices in the graph to become colored. This paper establishes a connection between dynamic monopolies and the well-known feedback vertex sets which are sets of vertices whose removal results in an acyclic graph. More specifically, we show that dynamic monopolies and feedback vertex sets are equivalent in graphs wherein all vertices have degree 2 or 3. We use this equivalence to provide exact values for the minimum size of dynamic monopolies of planar hexagonal grids, as well as upper and lower bounds on the minimum size of dynamic monopolies of cylindrical and toroidal hexagonal grids. For these last two topologies, the respective upper and lower bounds differ by at most one.     

Minimum Degree Orderings

It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called a flat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

A graph-based framework for sub-pixel image segmentation

Many image segmentation methods utilize graph structures for representing images, where the flexibility and generality of the abstract structure is beneficial. By using a fuzzy object representation, i.e., allowing partial belongingness of elements to image objects, the unavoidable loss of information when representing continuous structures by finite sets is significantly reduced, enabling feature estimates with sub-pixel precision.This work presents a framework for object representation based on fuzzy segmented graphs. Interpreting the edges as one-dimensional paths between the vertices of a graph, we extend the notion of a graph cut to that of a located cut, i.e., a cut with sub-edge precision. We describe a method for computing a located cut from a fuzzy segmentation of graph vertices. Further, the notion of vertex coverage segmentation is proposed as a graph theoretic equivalent to pixel coverage segmentations and a method for computing such a segmentation from a located cut is given. Utilizing the proposed framework, we demonstrate improved precision of area measurements of synthetic two-dimensional objects. We emphasize that although the experiments presented here are performed on two-dimensional images, the proposed framework is defined for general graphs and thus applicable to images of any dimension.     

Finding the Maximum Cut by the Greedy Algorithm

The paper considers the problem of finding the maximum cut on graphs. A new model of the problem is given in terms of the base of polymatroid. It is shown that the problem solution can be found by the greedy algorithm after the optimal linear ordering of the vertices has been determined.     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

Linear-Time Algorithms for Partial \boldmathk -Tree Complements

It is known that a graph decision problem can be solved in linear time over partial k -trees if the problem can be defined in Monadic Second-order (or MS) logic. MS logic allows quantification of vertex and edge subsets, with respect to which logical sentences can encode many different conditions that an input graph must satisfy. It is not always clear, however, which graph problems can be expressed in such a way. In this paper we consider problems stated as logical conditions on subsets of the vertices and nonedges of the input graph. If such a problem can be defined in MS logic (i.e., in terms of the vertices and edges of the input graph), then there is a linear-time algorithm to solve the problem over partial k -trees. This algorithm also provides a solution to some problem over the graph-theoretic complements of partial k -trees. We study several examples of these ``complement-problems.' We introduce a variation of MS logic in which, if a graph-problem can be defined over the class of partial k -tree complements, then there is a linear-time algorithm to solve that problem over partial k -tree complements, and (equivalently) a linear-time algorithm to solve its complement-problem over partial k -trees.     

基于高阶累计统计量的微生物发酵过程监测

传统多向核独立成分分析(MKICA)方法的实质是把基于独立成分分析(ICA)中的白化处理主元分析(PCA)替换为核主元分析(KPCA)后利用二阶统计量进行过程监控,并未利用过程数据的阶段特性和高阶累积量信息,为了解决此问题,提出高阶累积量分析(HCA)与多向核熵独立成份分析(MKECA)相结合的多向高阶累计量的核熵独立成分分析方法(HCA-MKEICA).首先,采用核熵独立成份分析(KECA)对原始数据进行数据转换,解决数据的非线性;然后,在高维核熵空间利用HCA技术构建新的统计量用于过程监控;最后,将该方法应用于青霉素仿真平台和实际的工业过程并与MKICA方法进行对比,以验证所提出方法的有效性.