Constrained-Path Labellings on Graphs of Bounded Clique-Width

Given a graph G we consider the problem of preprocessing it so that given two vertices x,y and a set X of vertices, we can efficiently report the shortest path (or just its length) between x,y that avoids X. We attach labels to vertices in such a way that this length can be determined from the labels of x,y and the vertices X. For a graph with n vertices of tree-width or clique-width k, we construct labels of size O(k ²log ² n). The constructions extend to directed graphs. The problem is motivated by routing in networks in case of failures or of routing policies which forbid certain paths.     

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

Hierarchical decompositions of graphs are interesting for algorithmic purposes. There are several types of hierarchical decompositions. Tree decompositions are the best known ones. On graphs of tree-width at most k , i.e., that have tree decompositions of width at most k , where k is fixed, every decision or optimization problem expressible in monadic second-order logic has a linear algorithm. We prove that this is also the case for graphs of clique-width at most k , where this complexity measure is associated with hierarchical decompositions of another type, and where logical formulas are no longer allowed to use edge set quantifications. We develop applications to several classes of graphs that include cographs and are, like cographs, defined by forbidding subgraphs with ``too many' induced paths with four vertices. Received April 13, 1998, and in revised form June 22, 1999, and in final form August 20, 1999.     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes

We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.     

基于限界传递相似度图的FCA概念相似度计算方法

使用相似度图计算FCA概念相似度需要构造相似关系的传递闭包,对于复杂问题会导致相似度图规模过大,从而影响相似度评价的效率.为了降低相似度图规模,提出一种基于限界传递相似度图的FCA概念相似度计算方法.该方法首先通过限定传递相似关系的长度来避免构造相似关系的传递闭包,得到的限界传递相似度图中忽略了长度超过界限且对区分FCA概念无用的传递相似关系,能够有效压缩相似度图的规模;然后给出了动态传递相似度计算方法和由限界传递相似度图构建二部图的方法.实验结果表明,使用限界传递相似度图能够在不损失计算结果准确度的情况下有效提高FCA概念相似度计算的效率.     

On Dissemination Thresholds in Regular and Irregular Graph Classes

We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < \frac12p<\frac{1}{2} . We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.     

Clique-Width for 4-Vertex Forbidden Subgraphs

Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. The notion of clique-width extends the one of treewidth, since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.     

Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line

Two vertices of an undirected graph are called k -edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k -edge-connectivity or k -edge-connected components. This paper describes graph structures relevant to classes of 4 -edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and n Insert-Vertex and m Insert-Edge updates can be performed in O(q + m + n log n) total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k -edge-connectivity (k arbitrary) in a (k-1) -edge-connected graph is presented. Its complexity is O(q + m + n) , with O(M +k ² n log (n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices. Received July 5, 1995; revised October 21, 1996.     

二分类图上的非冗余协同图模式挖掘算法

图模式广泛应用于构建高效图分类模型的特征空间识别．协同图模式是一种内部节点高度相关的图结构,与普通图模式相比,协同图模式具有更高的区分能力,从而更加适用于分类模型的特征选择．文中研究了从二分类图中挖掘非冗余协同图模式的问题,通过限制协同图模式的区分能力远远高于其所有子图模式的非冗余性质,大幅度减少了挖掘结果的数量,同时保留了具有强区分能力的协同图模式．由于协同图模式理论上必须检测其所有子图是否满足约束条件,挖掘它们非常具有计算挑战性．基于非冗余协同图模式的多种特性,提出相对应的削减规则;通过对区分能力的边界估计,提出两个快速检测非冗余协同图模式方法,在此基础上给出了一种高效的深度优先挖掘算法 GINS．大量真实与合成数据集上的实验结果表明,GINS 算法明显优于其他两个代表性算法,作为图分类模型的分类特征时,非冗余协同图模式获得了较高的分类精度．     

两类网络图的边-平衡指数集

在较小次幂圈嵌套网络图的基础上,研究了10次幂嵌套网络图的边-平衡指数集。利用基础图、带齿套圈子图、单点扇形子图设计新思路,降低了构造标号图的复杂程度。当n=10为偶数时,提出了新的变换指数方法,简化了证明过程。确定了m模6余1和余3且m大于等于2时(m为圈数)无限路10次幂圈嵌套图的边-平衡指数集,并且解决了这两类幂圈嵌套图的边-平衡指数集的存在性,给出了具体构造方法和公式证明。     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

基于有向同步交互图的类族测试用例生成算法

根据类对象之间的消息通信产生的同步消息、消息传递以及消息等待的交互特征,设计了一种有向同步交互图(DSIG)模型,提出了类继承的同步交互路径(SIAPaths)测试用例生成方法,给出了自动生成同步交互路径的算法.同时,提出了同步交互序列测试充分性准则,并从基本交互路径序列和基本交互消息序列的测试覆盖率两方面阐述了测试的可行性.     

基于图神经网络的软件系统中关键类的识别

软件系统中通常存在一些在拓扑结构上处于核心位置的关键类,这些类上的缺陷往往会给系统带来极大的安全隐患,识别关键类对工程师理解或维护一个软件系统至关重要.针对这一问题,提出一种基于图神经网络的关键类识别方法.首先利用复杂网络理论,将软件系统抽象为软件网络;其次结合无监督网络节点嵌入学习以及邻域聚合的方式,构建一个编码-解码(encoder-decoder)框架,提取软件系统中类节点的表征向量;最后利用Pairwise排序学习实现网络中节点的重要性排序,从而实现软件系统中关键类的识别.为验证所提方法的有效性,选取4个Java开源软件作为实验对象,并与常用的5种节点重要性度量方法以及2个已有工作进行对比分析.实验结果表明:与介数中心性、K-core、接近中心性、节点收缩法和PageRank等方法相比,该方法识别关键类的效果更好;另外,相比已有工作,在前15％的关键类节点中,所提方法的召回率和准确率的提高幅度均在10％以上.     

New Tractable Classes From Old

The constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. This paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to synthesise larger, more expressive tractable classes. We demonstrate that the classes so obtained are genuinely novel, and have not been previously identified. In addition, we use algebraic techniques to extend the tractable classes which we identify, and to show that the algorithms for solving these extended classes can be less than obvious.     

基于UML类图的类之间依赖关系图论问题研究

首先简单介绍了UML的类图,并细分类之间依赖关系为数据依赖和方法依赖,在此基础上,将UML类图转化为有向依赖图,并依据图论理论来分析和研究了有向依赖图的性质和特点,证明了有向依赖图不是自反的,也不是反自反的;既不是对称的,也不是反对称的;不是传递的。     

两类新推进排序算法

排序学习算法的目标是得到最优排序函数,它给每个实例一个得分,并根据得分排定各实例的先后次序。在推进排序算法的框架下,允许学习存在一定程度的误差。设定正数ε作为允许误差的范围,用对称ε-insensitive指数亏损函数和对称ε-insensitive对数亏损函数替换原来的指数亏损函数,得到新算法。实验表明新算法是有效的。     

A New Ward BRDF Model with Bounded Albedo

Due to its realistic appearance, computational convenience, and efficient Monte Carlo sampling, Ward's anisotropic BRDF is widely used in computer graphics for modeling specular reflection. Incorporating the criticism that the Ward and the Ward‐Dür model do not meet energy balance at grazing angles, we propose a modified BRDF that is energy conserving and preserves Helmholtz reciprocity. The new BRDF is computationally cheap to evaluate, admits efficient importance sampling, and thus sustains the main benefits of the Ward model. We show that the proposed BRDF is better suited for fitting measured reflectance data of a linoleum floor used in a real‐world building than the Ward and the Ward‐Dür model.     

有界恢复模型下弹性泄露签名的新构造

弹性泄露密码学是当前密码学研究的热点.给出一个弹性泄露签名的定义,该定义是标准签名定义的一个扩展.构造一个有界恢复模型下的弹性泄露签名方案,并在标准模型下证明了它的安全性.本文的方案基于双线性配对的弹性泄露签名,结合了一次签名和Waters签名的特,通过改进,长度可大大缩短,克服了一次签名签名长度过长的缺点,具有较好的实用价值.