|
In computer science and graph theory, the method of color-coding〔Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994). STOC '94. ACM, New York, NY, 326–335. DOI= http://doi.acm.org/10.1145/195058.195179〕〔Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI= http://doi.acm.org/10.1145/210332.210337〕 efficiently finds -vertex simple paths, -vertex cycles, and other small subgraphs within a given graph using probabilistic algorithms, which can then be derandomized and turned into deterministic algorithms. This method shows that many subcases of the subgraph isomorphism problem (an NP-complete problem) can in fact be solved in polynomial time. The theory and analysis of the color-coding method was proposed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick. ==Results== The following results can be obtained through the method of color-coding: * For every fixed constant , if a graph contains a simple cycle of size , then such cycle can be found in: * * O() expected time, or * * O() worst-case time, where is the exponent of matrix multiplication.〔Coppersmith–Winograd Algorithm〕 * For every fixed constant , and every graph that is in any nontrivial minor-closed graph family (e.g., a planar graph), if contains a simple cycle of size , then such cycle can be found in: * * expected time, or * * worst-case time. * If a graph contains a subgraph isomorphic to a bounded treewidth graph which has vertices, then such a subgraph can be found in polynomial time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Color-coding」の詳細全文を読む スポンサード リンク
|