PCBN: a high-performance partitionable circular bus network fordistributed systems

The authors present a dynamically partitionable circular bus network (PCBN) and efficient algorithms for maximizing its utilization. In their approach, a distributed network is transformed into a graph, in which a vertex represents a communication request and an edge denotes the conflict between a pair of communication requests. A graph traversal algorithm is applied to the graph to identify some maximal independent sets of vertices. The communication requests corresponding to the vertices of a maximum independent set call proceed in parallel. By computing the expected size of the maximal independent sets of a graph, the improvement ratio of the network can be obtained. The network control and synchronization techniques of PCBN are described in detail. The idling problem in the execution of nonconflicting requests is also discussed     

On Independent Sets and Bicliques in Graphs

Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. In this paper we improve Prisner’s upper bound on the number of maximal bicliques (Combinatorica, 20, 109–117, 2000) and show that the maximum number of maximal bicliques in a graph on n vertices is Θ(3 ^n/3). Our major contribution is an exact exponential-time algorithm. This branching algorithm computes the number of distinct maximal independent sets in a graph in time O(1.3642 ⁿ ), where n is the number of vertices of the input graph. We use this counting algorithm and previously known algorithms for various other problems related to independent sets to derive algorithms for problems related to bicliques via polynomial-time reductions.     

A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically

In this paper we present a depth first search algorithm to generate the family of maximal independent sets of an undirected graph lexicographically. Extensive computational experience on more than 1000 randomly generated graphs ranging from 20 to 220 vertices and from 20% to 90% density has shown that the proposed algorithm is (a) two to fifteen times faster than the Bron and Kerbosch algorithm and (b) at least three times faster than the algorithm of Tsukiyamaet al. and becomes increasingly more efficient as both the density and size of the graph increase. A further characteristic of the proposed algorithm is that it employs four one-dimensional arrays of working computer memory only, each of which has length equal to the number of vertices of the graph.     

基于谱方法的无向赋权图剖分算法*

在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanczos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最     

Acyclic colorings of subcubic graphs

It is known that the acyclic chromatic number of a subcubic graph is at most four, and its acyclic edge chromatic number is at most five. We present algorithms that prove these two facts. Let n be the number of vertices of a graph. Our first algorithm takes O(n) time and uses four colors to properly color the vertices of any subcubic graph so that there is no 2-colored cycle. Our second algorithm takes O(n) time and uses five colors to properly color the edges of any subcubic graph so that there is no 2-colored cycle. Both are the first linear-time algorithms for the problems they solve.     

随机图的均匀边染色算法

图的均匀边染色是指图中任意两条相邻的边都分配到不同的颜色,且任意两个色类的颜色个数最大相差1。对图 进行均匀边染色所需的最少颜色数叫做 的均匀边色数。本文提出了一种启发式算法,能够求解图的最小均匀边色数。该算法根据均匀边染色条件,设计了两个子目标函数和一个总目标函数,借助染色矩阵的色补矩阵迭代交换,逐步寻优,直到找到最优解时结束。本文给出了详细的算法设计流程,并且进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定点数的图的最小均匀边色数,算法时间复杂度不超过 。     

随机图的邻点可区别VI-均匀全染色算法

邻点可区别[VI]-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类（点或边）的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别[VI]-均匀全色数。提出了一种针对随机图的邻点可区别[VI]-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别[VI]-均匀全色数。     

Adaboost和随机图划分的无监督图像分类

针对当前大多数无监督图像分类方法不能对每个图像类进行特征选择和自动确定图像类别的数量问题,提出一种基于Adaboost和随机图划分的无监督图像分类方法。该方法包括两个部分:1)将图像分类问题看做是一个自动的随机图划分问题,其中图的每一个顶点代表一幅图像,通过划分形成的子图代表了图像类。再采用Ada-boost算法对每一个形成的图像类进行特征选择,从而得到每类图像的表达模型。2)采用一种基于蒙特卡洛马尔可夫链(MCMC)的随机采样算法(SWC)来对图进行划分。相比传统的随机采样算法,SWC具有更快的收敛速度。在两个图像数据集上的实验结果表明,本文方法的分类性能明显优于其他现有的无监督分类法。     

Acyclic coloring of graphs of maximum degree five: Nine colors are enough

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.     

t-Wise independence with local dependencies

In this note we prove a large deviation bound on the sum of random variables with the following dependency structure: there is a dependency graph G with a bounded chromatic number, in which each vertex represents a random variable. Variables that are represented by neighboring vertices may be arbitrarily dependent, but collections of variables that form an independent set in G are t-wise independent.     

Coloring large graphs based on independent set extraction

This paper presents an effective approach (EXTRACOL) to coloring large graphs. The proposed approach uses a preprocessing method to extract large independent sets from the graph and a memetic algorithm to color the residual graph. Each preprocessing application identifies, with a dedicated tabu search algorithm, a number of pairwise disjoint independent sets of a given size in order to maximize the vertices removed from the graph. We evaluate EXTRACOL on the 11 largest graphs (with 1000 to 4000 vertices) of the DIMACS challenge benchmarks and show improved results for four very difficult graphs (DSJC1000.9, C2000.5, C2000.9, C4000.5). The behavior of the proposed algorithm is also analyzed.     

参考节点嵌入最短距离估算在图聚类中的应用

为解决社会关系网络图中节点没有坐标值、不能采用传统的欧几里得距离和曼哈坦距离进行聚类的问题,提出采用最短路径算法,来衡量点与点之间的相异度.针对最短路径算法具有时间复杂度大的缺点,引入基于参考节点嵌入的最短距离估算思想来估算两点之间的近似距离.在此基础上,针对DBLP数据集构成的社会关系网络图进行聚类,使用基于划分的k-medoids算法,分别采用以上两种距离算法,比较其优劣.实验证明改进后的算法和最短路径算法中的Dijkstra 算法相比,距离误差率小,时间复杂度大大降低,在提高效率的同时,取得了同样好的聚类效果.     

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

The problem of computing the chromatic number of a P ₅-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P ₅-free graph admits a k-coloring, and finding one, if it does.     

知识图谱划分算法研究综述

知识图谱是人工智能的重要基石,因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系,其中顶点表示实体,边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作,对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长,如何对其进行划分已成为目前知识图谱研究的热点问题.从知识图谱和图划分的定义出发,系统性地介绍当前知识图谱数据划分的各类算法,包括基本、多级、流式、分布式和其他类型图划分算法.首先,介绍4种基本图划分算法:谱划分算法、几何划分算法、分支定界算法、KL及其衍生算法,这类算法通常用于小规模图数据或作为其他划分算法的一部分;然后,介绍多级图划分算法,这类算法对图粗糙化后进行划分再投射回原始图,根据粗糙化过程分为基于匹配的算法和基于聚合的算法;其次,描述3种流式图划分算法,这类算法将顶点或边加载为序列后进行划分,包括Hash算法、贪心算法、Fennel算法,以及这3种算法的衍生算法;再次,介绍以KaPPa、JA-BE-JA和轻量级重划分为代表的分布式图划分算法及它们的衍生算法;同时,在其他类型图划分算法中,介绍近年来新兴的2种图划分算法:标签传播算法和基于查询负载的算法.通过在合成与真实知识图谱数据集上的丰富实验,比较了5类知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异,分析实验结果并推广到推理层面,获得了基于实验的知识图谱划分算法性能评价结论.最后,在对已有方法分析和比较的基础上,总结目前知识图谱数据划分面临的主要挑战,提出相应的研究问题,并展望未来的研究方向.     

GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem

This paper presents a new solver for the exactly one-in-a-set Generalized Traveling Salesman Problem (GTSP). In the GTSP, we are given as input a complete directed graph with edge weights, along with a partition of the vertices into disjoint sets. The objective is to find a cycle (or tour) in the graph that visits each set exactly once and has minimum length. In this paper we present an effective algorithm for the GTSP based on adaptive large neighborhood search. The algorithm operates by repeatedly removing from, and inserting vertices in, the tour. We propose a general insertion mechanism that contains as special cases the well-known nearest, farthest and random insertion mechanisms. We provide extensive benchmarking results for our solver in comparison to the state-of-the-art on a wide range of existing and new problem libraries. We show that on the GTSP-LIB library, the proposed algorithm is competitive with the best known algorithms. On several other libraries, we show that given the same amount of time, the proposed solver finds higher quality solutions than existing approaches, particularly on harder instances that are non-metric and/or whose sets are not clustered.     

求解图的最大独立集的一种算法

如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) )     

Finding the closed partition of a planar graph

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n^1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707.     

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

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。     

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.     

AnO(n 3) recognition algorithm for bithreshold graphs

A bithreshold graph is the edge intersection of two threshold graphs such that every independent set is independent in at least one of the threshold components. Recognizing a bithreshold graph is polynomially equivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and of the edges of a cobithreshold graph that leads to a recognition and decomposition algorithm. This algorithm works inO(n ³) time improving the previously knownO(n ⁴) result [HM].