论文标题
顶点订购图形着色问题的算法
Vertex Ordering Algorithms for Graph Coloring Problem
论文作者
论文摘要
图形着色是与许多实践中许多应用程序组合的基本问题。在此问题中，必须通过使用最少的颜色以使顶点具有与邻居不同的颜色的方式来颜色。该问题及其不同的变体已被证明是NP-HARD。因此，文献中有贪婪的算法，目的是使用少量颜色。这些算法穿越顶点并一一将其上色。顶点访问顺序对所使用的颜色数量有重大影响。在这项工作中，我们调查了社交网络分析指标是否可以用于找到此顺序。我们的实验表明，当使用紧密的中心性找到顶点访问顺序时，贪婪算法使用少量颜色。
Graph coloring is a fundamental problem in combinatorics with many applications in practice. In this problem, the vertices in a given graph must be colored by using the least number of colors in such a way that a vertex has a different color than its neighbors. The problem, as well as its different variants, has been proven to be NP-Hard. Therefore, there are greedy algorithms in the literature aiming to use a small number of colors. These algorithms traverse the vertices and color them one by one. The vertex visit order has a significant impact on the number of colors used. In this work, we investigated if social network analytics metrics can be used to find this order. Our experiments showed that when closeness centrality is used to find vertex visit order, a smaller number of colors is used by the greedy algorithms.
