Isometric-path numbers of block graphs

An isometric path between two vertices in a graph G is a shortest path joining them. The isometric-path number of G, denoted by ip(G), is the minimum number of isometric paths required to cover all vertices of G. In this paper, we determine exact values of isometric-path numbers of block graphs. We also give a linear-time algorithm for finding the corresponding paths.  

Automated generation of simply connected solid objects from wire-frame data using operations on graphs

This paper presents an algorithm for the automatic generation of solid objects from three-dimensional wire-frame data. In this work, as we mainly use topological information of wire-frame data, we can achieve high-speed execution and adapt this algorithm to free-from surfaces. We present the conversion algorithm and show several experimental results.  

一种P2P环境下点割集的被动分布式发现算法

P2P系统的可靠性主要取决于覆盖网节点间的连通性,而割点和小规模点割集对网络连通性的危害很大,它们的失效或离开能使覆盖网变得四分五裂。本文提出一种P2P环境下点割集的被动分布式发现算法,在无法获得网络全局信息的情况下,节点仅依靠对收到消息的统计和分析就能够自主判断自己是否为割点或属于2点割,并采取相应措施消除其为系统带来的不稳定因素。该算法准确性高、开销低,割集消除对提高覆盖网可靠性的效果显著。  

一种简单的图的平面性判断算法的实现研究

Malgrange、Malgrange和Pertuiset三人合作提出O（n2）时间复杂度的平面性判断算法，尽管效率不是那么理想，却易于理解，并且算法结束时能够给出平面图的一种平面嵌入，另外算法仅涉及到割点的检测、图的计算机表示、图的分割、图的遍历等较为基础的问题。从而能够很好地适应教学及入门对直观性，可实现性的需要。尽管这个方法已经较为直观。但是由于图的平面嵌入在计算机中的表示较为困难等问题．其算法具体如何实现依然需要细心研究。  

无向关系图视觉清晰化显示算法

本文提出了一种无向图视觉清晰化显示算法,使一般的无向关系图经过该算法重新确定顶点位置后,能得到清晰美观的输出结果。该算法首先将无向关系图去除孤立点,分离连通分支,并通过识别割边将每个连通分支分解成一系列的团,每个团内无割边,这些团以树型结构连接;然后通过识别割点和虚连线将每个团分解成子团,每个子团内无割点;最后将子团内顶点均匀分布在一个圆环上。该算法的优点在于实现方便,方法简单,运行高效,输出结果美观,并易于并行化。  

基于右手法则的网络割点判定算法

分析了网络割点的分布式判定算法中的主动探测法和被动探测法,提出了基于右手法则的网络边界探测算法以及基于该算法的网络割点判定算法,并给出了算法的正确性证明。分析表明,上述算法涉及的节点较少,能有效降低通信开销,有利于提高网络的稳定性。  

基于压缩的大规模图的割点求解算法

割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.  

无线传感器与执行器网络基于邻居信息的割点检测算法

无线传感器与执行器网络（WSANs）中通信关键节点（割点）对网络的连通性和通信性能有着重要影响，迅速准确的割点检测以及在此基础上的拓扑修复是提高鲁棒性、保证网络通信性能的重要前提。提出了一种分布式割点检测算法（DCVN），该算法中每个节点通过至多与其两跳邻居节点进行信息交换来建立局部的网络拓扑信息，再根据预设的判断准则来实现对WSANs中的割点的快速检测。实验模拟显示该算法能够很好的满足割点的检测需求，在检测准确率方面要优于现有的几种有代表性的割点检测算法。