论文标题
使用Pagerank计算反馈弧集
Computing a Feedback Arc Set Using PageRank
论文作者
论文摘要
我们提出了一种新的启发式算法，用于计算有向图中设置的最小反馈弧。新技术生产的解决方案比最佳以前已知的启发式方法所产生的解决方案更好，通常将FAS尺寸降低了50％以上。它基于计算输入有向图的有向线图的节点的Pagerank评分。尽管我们的启发式启发式所需的时间受到生产线图的大小的影响很大，但我们的实验结果表明，即使对于图形图中使用的非常大的图，它的运行也非常快。
We present a new heuristic algorithm for computing a minimum Feedback Arc Set in directed graphs. The new technique produces solutions that are better than the ones produced by the best previously known heuristics, often reducing the FAS size by more than 50%. It is based on computing the PageRank score of the nodes of the directed line graph of the input directed graph. Although the time required by our heuristic is heavily influenced by the size of the produced line graph, our experimental results show that it runs very fast even for very large graphs used in graph drawing.
