论文标题
用于着色图的统一算法
A unified algorithm for colouring graphs of bounded clique-width
论文作者
论文摘要
集团宽度是导致多项式特殊案例算法的图形复杂度度量之一，例如通常NP完整问题，例如图形性。目前最佳的两种已知算法用于验证表示为集团宽度术语的图形的C色，以针对两种不同的极端情况，恒定的颜色和大量颜色进行了优化。我们提出了一种在两种情况下都可以达到艺术复杂性的单个相对简单算法中统一这些方法的方法。统一算法还为大量颜色提供了加速。
Clique-width is one of the graph complexity measures leading to polynomial special-case algorithms for generally NP-complete problems, e.g. graph colourability. The best two currently known algorithms for verifying c-colourability of graphs represented as clique-width terms are optimised towards two different extreme cases, a constant number of colours and a very large number of colours. We present a way to unify these approaches in a single relatively simple algorithm that achieves the state of the art complexity in both cases. The unified algorithm also provides a speed-up for a large number of colours.
