Color-coding
http://dbpedia.org/resource/Color-coding an entity of type: Abstraction100002137
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.
rdf:langString
Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину.
rdf:langString
rdf:langString
Color-coding
rdf:langString
Цветовое кодирование
xsd:integer
22469695
xsd:integer
1115906832
rdf:langString
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.
rdf:langString
Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину. Метод цветового кодирования предложили и анализировали в 1994 году. Авторы-Нога Алон, Рафаэль Юстер и Юрий Цвик.
xsd:nonNegativeInteger
13747