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.
翻译： clique-width 是图形复杂度的尺度之一, 导致对一般NP- 完整的问题( 例如, 图形色度) 采用多元特写算法。 用于校验以 cloque- wird 术语表示的图形的c色度的目前已知最佳两种算法被优化为两种不同的极端情况, 一种是固定的颜色, 另一种是非常多的颜色。 我们提出一种方法, 将这些方法统一成一个单一的相对简单的算法, 以达到两种情况下的艺术复杂性。 统一的算法也为大量颜色提供了加速的功能 。
相关内容
微信扫码咨询专知VIP会员