Honour Thy Neighbour: Clique Maintenance in Dynamic Graphs
Honour Thy Neighbour: Clique Maintenance in Dynamic Graphs
复制标题
尊重你的邻居：动态图中的派系维护
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Jirí Vomlel
中科院分区：
文献类型：
--
作者：
Thorsten J. Ottosen;Jirí Vomlel
当对象及其交互通过无向图建模时，了解图的团通常是非常有趣的。对于几个问题的图形经常随着时间的推移而变化，因此，我们寻求的方法更新的信息集团在一个动态的方式，以避免昂贵的重新计算。这一动态问题的研究Stix，在本文中，我们推导出一个新的简单的方法的基础上的布朗Kerbosch算法，媲美Stix的方法。新方法是通用的，因为它可以与其他算法一起使用，而不仅仅是Bron-Kerbosch。应用包括模糊聚类和贝叶斯网络的最优三角剖分。
Whenever objects and their interaction is modelled via undirected graphs, it is often of great interest to know the cliques of the graph. For several problems the graph changes frequently over time, and we therefore seek methods for updating the information about the cliques in a dynamic fashion to avoid expensive recomputations. This dynamic problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix’ approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. The applications include fuzzy clustering and optimal triangulation of Bayesian networks.