论文标题
从任意图生成弱弦图
Generating Weakly Chordal Graphs from Arbitrary Graphs
论文作者
论文摘要
我们提出了一种从随机生成的输入图（v，e）生成弱弦图的方案。我们使用最小顶点启发式术，通过添加填充边缘添加填充边缘将g降低到弦图H。由于H必定是一个弱弦的图形，因此我们使用算法从弱的弦图中删除边缘，该图形保留了H。HH的弱弦属性属性。删除候选的边缘是插入G的填充边缘。从队列的正面删除了一个填充边缘，然后我们尝试从H中删除。如果这违反了H的较弱的串联属性，我们将其重新插入了队列后面的边缘。该循环一直持续到无法从H中删除H.在操作上，我们通过将删除回合定义为前部的边缘在前面的边缘来实现。
We propose a scheme for generating a weakly chordal graph from a randomly generated input graph, G = (V, E). We reduce G to a chordal graph H by adding fill-edges, using the minimum vertex degree heuristic. Since H is necessarily a weakly chordal graph, we use an algorithm for deleting edges from a weakly chordal graph that preserves the weak chordality property of H. The edges that are candidates for deletion are the fill-edges that were inserted into G. In order to delete a maximal number of fill-edges, we maintain these in a queue. A fill-edge is removed from the front of the queue, which we then try to delete from H. If this violates the weak chordality property of H, we reinsert this edge at the back of the queue. This loop continues till no more fill-edges can be removed from H. Operationally, we implement this by defining a deletion round as one in which the edge at the back of the queue is at the front.We stop when the size of the queue does not change over two successive deletion rounds and output H.
