Color-coding
In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. The color-coding method was proposed and analyzed in 1994 by Noga Alon, , and Uri Zwick.
- Comment
- enIn computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. The color-coding method was proposed and analyzed in 1994 by Noga Alon, , and Uri Zwick.
- Has abstract
- enIn computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length k in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. Color-coding also applies to the detection of cycles of a given length, and more generally it applies to the subgraph isomorphism problem (an NP-complete problem), where it yields 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, , and Uri Zwick.
- Is primary topic of
- Color-coding
- Label
- enColor-coding
- Link from a Wikipage to another Wikipage
- Algorithmic technique
- Aravind Srinivasan
- Category:Graph algorithms
- Computer science
- Cycle (graph theory)
- Derandomization
- Graph theory
- Jeanette P. Schmidt
- Leonard J. Schulman
- Matrix multiplication
- Minor (graph theory)
- Moni Naor
- NC (complexity)
- Network motif
- Noga Alon
- NP-complete
- Path (graph theory)
- Perfect hash
- Planar graph
- Planar graphs
- Polynomial time
- Probabilistic algorithms
- Protein-protein interaction
- Raphael Yuster
- Structural motif
- Subgraph isomorphism
- Treewidth
- Uri Zwick
- Wnt signaling pathway
- SameAs
- 4iE5f
- Color-coding
- Kodiranje bojama
- m.05zp14w
- Q5148529
- Цветовое кодирование
- Subject
- Category:Graph algorithms
- WasDerivedFrom
- Color-coding?oldid=1115906832&ns=0
- WikiPageLength
- 13747
- Wikipage page ID
- 22469695
- Wikipage revision ID
- 1115906832
- WikiPageUsesTemplate
- Template:!
- Template:=
- Template:About
- Template:Cite journal
- Template:Math
- Template:Mvar
- Template:Reflist
- Template:Sfrac