Color-coding – link to Isomorphism problem

It is not possible to add the new link because it would replace an existing, longer link.

Line 2:

In [[computer science]] and [[graph theory]], the term '''color-coding''' refers to an [[algorithmic technique]] which is useful in the discovery of [[Network motif|network motifs]]. For example, it can be used to detect a [[Path (graph theory)|simple path]] of length {{mvar|k}} in a given [[graph theory|graph]]. The traditional color-coding algorithm is [[probabilistic algorithms|probabilistic]], but it can be [[Derandomization#Derandomization|derandomized]] without much overhead in the running time.

Color-coding also applies to the detection of [[Cycle (graph theory)|cycles]] of a given length, and more generally it applies to the [[~~subgraph isomorphism|subgraph~~ isomorphism problem]] (an [[NP-complete]] problem), where it yields [[polynomial time|polynomial time algorithms]] when the subgraph pattern that it is trying to detect has bounded [[treewidth]].

Color-coding also applies to the detection of [[Cycle (graph theory)|cycles]] of a given length, and more generally it applies to the subgraph [[isomorphism problem]] (an [[NP-complete]] problem), where it yields [[polynomial time|polynomial time algorithms]] when the subgraph pattern that it is trying to detect has bounded [[treewidth]].

The color-coding method was proposed and analyzed in 1994 by [[Noga Alon]], [[Raphael Yuster]], and [[Uri Zwick]].<ref>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</ref><ref name="orig">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</ref>

@@ Line 2: / Line 2: @@
 In [[computer science]] and [[graph theory]], the term '''color-coding''' refers to an [[algorithmic technique]] which is useful in the discovery of [[Network motif|network motifs]]. For example, it can be used to detect a [[Path (graph theory)|simple path]] of length {{mvar|k}} in a given [[graph theory|graph]]. The traditional color-coding algorithm is [[probabilistic algorithms|probabilistic]], but it can be [[Derandomization#Derandomization|derandomized]] without much overhead in the running time.
-Color-coding also applies to the detection of [[Cycle (graph theory)|cycles]] of a given length, and more generally it applies to the [[subgraph isomorphism|subgraph isomorphism problem]] (an [[NP-complete]] problem), where it yields [[polynomial time|polynomial time algorithms]] when the subgraph pattern that it is trying to detect has bounded  [[treewidth]].
+Color-coding also applies to the detection of [[Cycle (graph theory)|cycles]] of a given length, and more generally it applies to the subgraph [[isomorphism problem]] (an [[NP-complete]] problem), where it yields [[polynomial time|polynomial time algorithms]] when the subgraph pattern that it is trying to detect has bounded  [[treewidth]].
 The color-coding method was proposed and analyzed in 1994 by [[Noga Alon]], [[Raphael Yuster]], and [[Uri Zwick]].<ref>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</ref><ref name="orig">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</ref>