COLOR-CODING
COLOR-CODING
复制标题
DOI：
10.1145/210332.210337
复制
发表时间：
1995-07-01
期刊：
影响因子：
--
通讯作者：
ZWICK, U
中科院分区：
文献类型：
--
作者：
ALON, N;YUSTER, R;ZWICK, U
我们描述了一种新的随机化方法，颜色编码的方法，找到简单的路径和循环的指定长度k。和其他小的子图，在一个给定的图G =（V，E）。使用这种方法获得的随机化算法可以使用完美散列函数族进行去随机化。利用颜色编码的方法，我们得到了如下新结果：对于每个固定的k，如果图G =（V，E）包含一个大小正好为k的简单圈，那么这样的圈可以在O（V-omega）的期望时间或O（V-omega log V）的最坏情况时间内找到，其中omega < 2.376是矩阵乘法的指数。(Here在下文中，我们用V和E来代替\V\和\E\，只要不引起混淆。）对于每个固定的k，如果一个平面图G =（V，E）包含一个大小正好为k的简单圈，那么这样的圈可以在O（V）的期望时间或O（Vlog V）的最坏情况时间内找到。如果一个图G =（V，E）包含一个同构于一个有界树宽图H =（V-H，E（H））的子图，其中\V-H\ = O（log V），那么可以在多项式时间内找到H的这样一个副本。这是以前不知道的，即使H只是一个路径的长度为O（log V）。这些结果改善了许多作者以前的结果。第三个结果肯定地解决了Papadimitriou和Yannakakis的一个猜想，即路径问题在P中。
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k. and other small subgraphs, within a given graph G = (V, E). The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, in particular, the following new results:For every fixed k, if a graph G = (V, E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V-omega) expected time or O(V-omega log V) worst-case time, where omega < 2.376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead of \V\ and \E\ whenever no confusion may arise.)For every fixed k, if a planar graph G = (V, E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V) expected time or O(V log V) worst-case time. The same algorithm applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs.If a graph G = (V, E) contains a subgraph isomorphic to a bounded tree-width graph H = (V-H, E(H)) where \V-H\ = O(log V), then such a copy of H can be found in polynomial time. This was not previously known even if H were just a path of length O(log V).These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can show that it is even in NC.