共查询到18条相似文献,搜索用时 125 毫秒
1.
2.
一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。 相似文献
3.
基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径。将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询。本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径。实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内。 相似文献
4.
5.
6.
7.
从Internet拓扑的幂律特征(度分布律)出发,定义了主干子图的相关概念,证明了主干子图的若干性质,并在此基础上给出了基于主干子图的聚类算法。该算法可应用于有幂律特征的大型图的混合布局,也可为幂律特征网络的研究提供参考。幂律特征图可以被分解为一个主干子图和多个子树。主干子图是一些度相对较高节点的集合;而子树则正好相反,幂律特征有效地保证了节点度分布的非均一特性。基于主干子图理论的图聚类算法可以分成两个步骤,即主干子图生成算法和桩树生成算法。主干子图Gs(Vs,Es)与原始图G(V,E)之间的同态等价关系 相似文献
8.
9.
基于扩展影响图的超视距空战辅助决策方法 总被引:1,自引:0,他引:1
利用扩展影响图的表示特性和计算特性来解决辅助决策系统中知识表示与问题求解的一致性问题.采用条件弧和决策簇扩展影响图解决其在描述非对称性、不确定性问题中的局限,并根据该扩展影响图提出了基于条件分解的求解算法.基于扩展影响图方法对系统进行分析并描述系统结构,给出了基于扩展影响图进行辅助任务分析设计的框架和系统结构.仿真结果表明了所提出方法的有效性. 相似文献
10.
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向. 相似文献
11.
12.
根据图上节点所在位置与邻居节点特征,可以使用不同策略为每个图上节点进行区间编码,基于区间编码,许多在大型图上的应用如知识图谱查询、智能问答等的处理可以加速或得到准确性上的提升。针对此种情况,提出一种基于树分解算法的图上点区间编码方法,并在大型知识图谱上通过智能问答歧义消除的应用验证该方法的有效性。实验结果表明,该方法能够有效地表达出图上节点的位置特征,并帮助智能问答中的实体消除歧义。 相似文献
13.
Christoph Blume H.J. Sander Bruggink Martin Friedrich Barbara König 《Journal of Visual Languages and Computing》2013,24(3):192-206
We will revisit the categorical notion of cospan decompositions of graphs and compare it to the well-known notions of path decomposition and tree decomposition from graph theory. More specifically, we will define several types of cospan decompositions with appropriate width measures and show that these width measures coincide with pathwidth and treewidth. Such graph decompositions of small width are used to efficiently decide graph properties, for instance via graph automata. Hence we will give an application by defining graph-accepting tree automata, thus integrating previous work by Courcelle into the setting of cospan decompositions. Furthermore we will show that regardless of whether we consider path or tree decompositions, we arrive at the same notion of recognizability. 相似文献
14.
Modular decomposition is a technique that applies to (but is not restricted to) graphs. The notion of a module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to solve a large number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 1970’s, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research. 相似文献
15.
16.
17.
We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q. We present a lower bound and a genetic algorithm for the PCSTP. The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%. 相似文献