基于潜在组分配及对比学习增强的符号二值图神经网络

针对符号二值网络的节点异质性及三角形形式平衡理论不适用性的问题,提出一种基于潜在类分配及对比学习增强的符号二值图神经网络模型,其通过同质和异质双空间的互相补充来充分提取网络的隐式和显式信息。在同质空间,采用可学习的潜在组对节点进行分配并将节点看做多个潜在组的组合,然后通过训练来自动挖掘节点间的信息。在异质空间,对节点邻居进行有方向区分的注意力聚合,然后采用网络重建的互信息对比学习来引导聚合过程以获得表达能力更强的表示向量。在符号链接预测任务上与多种相关模型进行对比实验,实验结果显示所提出的模型在四个真实数据集上采用四种评价指标获取的16个评价结果中,12个评价结果可以取得最优值,验证了所提出模型的有效性。     

Maximal matching and edge domination in complete multipartite graphs

For any graph G, let α′(G) and α′_min(G) be the maximum cardinality and minimum cardinality among all maximal matchings in G, respectively, and let γ′(G) and γ_t ′(G) be the edge domination number and edge total domination number of G, respectively. In this paper, we first show some properties of maximal matchings and further determine the exact values of α′(G) and α′_min(G) for a complete multipartite graph G. Then, we disclose relationships between maximal matchings and minimal edge dominating sets, and thus obtain the exact values of γ′(G) and γ_t′(G) for a complete multipartite graph G.     

求图符号控制数的完全算法研究

确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五。对这两个算法也进行了比较。     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

Bipartite consensus of multi‐agent systems over signed graphs: State feedback and output feedback control approaches

This paper studies bipartite consensus problems for continuous‐time multi‐agent system over signed directed graphs. We consider general linear agents and design both state feedback and dynamic output feedback control laws for the agents to achieve bipartite consensus. Via establishing an equivalence between bipartite consensus problems and the conventional consensus problems under both state feedback and output feedback control approaches, we make direct application of existing state feedback and output feedback consensus algorithms to solve bipartite consensus problems. Moreover, we propose a systematical approach to design bipartite consensus control laws. Copyright © 2016 John Wiley & Sons, Ltd.     

求解区间图上的罗马控制数的动态规划算法

摘 要: 针对区间图的最小罗马控制函数和罗马控制数求解的困难性,本文提出了一个动态规划算法。从区间图的顶点排序开始,结合区间图的某些性质,采用逐步搜索的方法,不断扩大搜索的顶点集合范围,最终求出最优的罗马控制集和罗马控制数。为保证算法的正确性和科学性,对算法进行了严格的数学推理和证明。最后还给出了一个典型的区间图求解过程的演示示例,增强了算法的可读性和可操作性。结果表明该算法不仅运算速度快,而且简单易行。 关键词: 区间图;罗马控制函数;罗马控制数;权重;动态规划算法     

混合图的H-Estrada指标

混合图的Hermitian邻接矩阵是共轭矩阵,其全体特征值称为混合图的H-谱。借助该矩阵的许多性质能更有效地研究混合图。基于H-谱引出混合图的一个重要拓扑指标--H-Estrada指标。拟用数学分析的方法,对其性质做数理研究。     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.     

Edge crossings in drawings of bipartite graphs

Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed barycenter heuristic for this problem is analyzed. An alternative method, the median heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.