彩色编码技术的研究进展及应用

The Evolution and Application of Color-coding

作为一种重要的参数化技术,彩色编码技术得到了越来越多的重视并在近年来取得了理论和应用上的一系列进展。本文首先介绍了彩色编码技术的基本思想和相关定义,并详细论述了随机式和确定式两种彩色编码技术。最后本文具体介绍和分析了彩色编码技术在路径查找、子图同构、matching与packing、(t,n)-环签名等问题上的应用,并探讨了彩色编码技术及其应用的进一步研究工作。

As one of the most important FPT classification techniques, color-coding is attracting more and more research concerns and has achieved a series of breakthroughs both theoretically and pragmatically in recent years. This paper first introduces the essentials and related definitions of color-coding technique, and details the randomized and deterministic color-coding respectively. Then this paper makes a brief introduction to the application of color-coding in problems such as path-finding, subgraph isomorphism, matching＆packing and （t, n）-ring signature. Moreover, this paper makes a discussion on color-coding and its future works.