| dbo:abstract
|
- 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. 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. (en)
- Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину. Метод цветового кодирования предложили и анализировали в 1994 году. Авторы-Нога Алон, Рафаэль Юстер и Юрий Цвик. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13747 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 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. (en)
- Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину. (ru)
|
| rdfs:label
|
- Color-coding (en)
- Цветовое кодирование (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
