基于局部比值法的强弦图带权控制集问题的线性时间算法

一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。     

带权图的均衡 k划分

带权图的均衡 k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小。这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题。首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法。该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集 S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集 S的顶点权值之和满足要求。此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化。实验结果表明,当 k分别取值为2,4,8时所提算法分别在86％,81％,68％的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60％以上。     

广义Kautz有向图GK(3,n)的反馈数的界

对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即 f(3,n)≤n+5n8 － 3n4－ 4n7+3。     

d-子树划分问题

边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集,且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.     

一种人体三维Reeb图计算方法

提出一种人体三维Reeb计算方法。利用人体三维网格数据的顶点坐标,求取顶点的测地距离,构造Morse函数,依据顶点的三角面关系提取人体三维模型的Reeb图,给出基于Reeb图的一般人体骨架结构表示。通过计算Reeb图上弧的曲率,判断是否需要增加关节节点,从而能更准确地描述人体三维模型的拓扑结构。实验结果表明,该方法计算量小、适用性广。     

三角网格模型骨架提取算法

骨架图能够直观表达三维模型几何形状,很好地反映模型的拓扑特征,在工业机器人抓取、特征识别等领域有着广泛的应用。针对三角网格表达的工业零件给出一种骨架提取算法,该算法采用Reeb图对三角网格进行骨架的抽取运算。首先读取三角网格文件,并对复杂的三角网格进行简化处理,然后遍历所有的三角网格,采用Dijkstra算法抽取基本点集,根据定义的连续函数计算每个顶点的函数值,最后根据函数值得出模型的基本骨架。实验表明,该算法具有良好的计算效果和效率,提取出的骨架图较好地保存了三维模型拓扑结构和姿态,可作为后续研究三维模型搜索的特征描述符。     

基于近似最少切割面的凹多面体剖分算法

为了提高凹多面体的剖分效率、减少剖分后增加的顶点数和凹边数,利用回路提出一种对任意的凹多面体不添加任何顶点的有效的凸剖分方法。首先将凹多面体抽象成无向图,然后利用深度优先搜索策略找出由这个无向图的边所组成的最优回路,该回路上的边的个数最少,并且凹边个数多。由该回路上的边组成的一系列切面对凹多面体进行一次切割。该方法可以在对多面体不添加任何顶点的情况下找到近似最好的回路,形成近似最少的切割面,对多面体的切割接近最少,剖分后得到的多面体个数近似最少。     

基于多层k路划分的三维网格并行任务分配策略

为解决传统任务划分方法在三维网格并行计算任务分配阶段产生的通信开销大的问题,提出了一种基于多层k路划分算法的并行任务分配策略.首先利用多层k路划分算法划分三维网格,将任务划分问题转化为图划分问题,然后基于图划分结果给出一个任务映射并行算法将计算任务分配到各计算结点.在深腾1800上求解三维网格模型最短路径问题的实验结果表明,相比于传统的行列划分任务分配策略,该策略在保证负裁平衡的同时有效地降低了通信开销,算法的运行时间减少,加速比得到提高.     

文件时间问题——2003年第5期题解

问题描述见2003年第5期杂志。算法分析通过解读招聘问题我们不难发现它是一道简单的关于有条件的分类或划分问题,解这种问题的方法有很多。在这里我们介绍用图的着色和集合划分来解它。 1.图的着色在本问题中,我们把每一个部门作为顶点,如有应聘者同时应聘几个部门时,在这些部门之间相互连一条边,这样就得到一个图。我们对图的顶点进行着色,同色顶点安排在同一场面试,这样得到的着色数即为需要安排的最少场次。这样招聘     

基于三维网格模型的双重数字盲水印算法

为提高一重三维模型数字水印的安全性,提出一种基于三维网格模型的双重数字盲水印算法。通过改变三角网格顶点在其一环相邻顶点所确定的局部几何空间中的位置和三角面片顶点排列顺序,嵌入双重水印,使模型能抵抗严重的剪切攻击及一定程度的噪声攻击。算法在提取水印时无需原始模型。仿真结果表明,该算法能够有效抵抗平移、旋转、均匀缩放、顶点乱序、多边形乱序及剪切等攻击,具有嵌入可读水印的不可见性。     

How to Guard a Graph?

We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber’s or the cops’ regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber’s region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree (or even in a star), then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a directed acyclic graph, the problem becomes PSPACE-complete.     

Cops and Robber Game Without Recharging

Cops & Robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this work, we consider a natural variant of this game, where every cop can make at most f steps, and prove that for each f≥2, it is PSPACE-complete to decide whether k cops can capture the robber.     

The role of information in the cop-robber game

We investigate the role of the information available to the players on the outcome of the cops and robbers game. This game takes place on a graph and players move along the edges in turns. The cops win the game if they can move onto the robber’s vertex. In the standard formulation, it is assumed that the players can “see” each other at all times. A graph G$G$ is called cop-win if a single cop can capture the robber on G$G$. We study the effect of reducing the cop’s visibility. On the positive side, with a simple argument, we show that a cop with small or no visibility can capture the robber on any cop-win graph (even if the robber still has global visibility). On the negative side, we show that the reduction in cop’s visibility can result in an exponential increase in the capture time. Finally, we start the investigation of the variant where the visibility powers of the two players are symmetrical. We show that the cop can establish eye contact with the robber on any graph and present a sufficient condition for capture. In establishing this condition, we present a characterization of graphs on which a natural greedy pursuit strategy suffices for capturing the robber.     

Cops and robber on grids and tori: basic algorithms and their extension to a large number of cops

The Journal of Supercomputing - The studies of the classical cops and robber problem are generally aimed at determining the minimum number of cops needed to capture the robber, and proposing...     

Time constrained graph searching

We consider time constraints for four models of searching graphs for intruders. One model is the standard cops and robber vertex-searching model with complete visibility. The second model differs from the preceding one only in that none of the searchers can see the intruder. The third model is a vertex-searching model in which searchers and an intruder move simultaneously and none of the searchers can see the intruder. The fourth model is simultaneous edge searching with an arbitrarily fast intruder.     

Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c_k(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c_k from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c_k(G) values and develop an O(n^2s+3) algorithm for determining if c_k(G)≤s for s fixed. We prove that if s is not fixed, then computing c_k(G) is NP-hard. Upper and lower bounds are found for c_k(G) in terms of the order of G. We prove that

     

Black-white pebbles and graph separation

Summary We exhibit a close relationship between two topics in computational complexity. One topic is the analysis of storage requirements for nondeterministic computations. The corresponding mathematical model is a well known black-white pebble game on directed acyclic graphs. The other topic is the search for small separators of undirected graphs. We model a dynamic version of the concept of a separator with a vertex separator game. This game is closely related to graph layout and searching problems. We show that instances of the black-white pebble game and the vertex separator game can easily be transformed into each other. As an application of this result both games are shown to be NP-complete.     

Parameterized pursuit-evasion games

We study the parameterized complexity of four variants of pursuit-evasion on graphs: Seeded Pursuit Evasion, Short Seeded Pursuit Evasion, Directed Pursuit Evasion and Short Directed Pursuit Evasion. Both Seeded Pursuit Evasion and Short Seeded Pursuit Evasion are played on undirected graphs with given starting positions for both the cops and the robber. Directed Pursuit Evasion and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for Seeded Pursuit Evasion and Directed Pursuit Evasion that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (Short Seeded Pursuit Evasion and Short Directed Pursuit Evasion) are AW[*]-complete when we parameterize by both the number of cops and turns.     

Robust self-assembly of graphs

Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion (negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold, called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model. A natural question in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the completion of the assembly. We show that the robust self-assembly problem is co-NP-complete even on planar graphs with two distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled, and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。