| http://dbpedia.org/ontology/abstract
|
Цветовое кодирование — , которая полезна д … Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину. Метод цветового кодирования предложили и анализировали в 1994 году. Авторы-Нога Алон, Рафаэль Юстер и Юрий Цвик.торы-Нога Алон, Рафаэль Юстер и Юрий Цвик.
, In computer science and graph theory, the … 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.zed in 1994 by Noga Alon, , and Uri Zwick.
|
| http://dbpedia.org/ontology/wikiPageID
|
22469695
|
| http://dbpedia.org/ontology/wikiPageLength
|
13747
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1115906832
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Network_motif +
, http://dbpedia.org/resource/Planar_graphs +
, http://dbpedia.org/resource/Aravind_Srinivasan +
, http://dbpedia.org/resource/Computer_science +
, http://dbpedia.org/resource/Subgraph_isomorphism +
, http://dbpedia.org/resource/Cycle_%28graph_theory%29 +
, http://dbpedia.org/resource/Perfect_hash +
, http://dbpedia.org/resource/Protein-protein_interaction +
, http://dbpedia.org/resource/Treewidth +
, http://dbpedia.org/resource/Uri_Zwick +
, http://dbpedia.org/resource/NC_%28complexity%29 +
, http://dbpedia.org/resource/Matrix_multiplication +
, http://dbpedia.org/resource/Moni_Naor +
, http://dbpedia.org/resource/Structural_motif +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Noga_Alon +
, http://dbpedia.org/resource/Probabilistic_algorithms +
, http://dbpedia.org/resource/Raphael_Yuster +
, http://dbpedia.org/resource/Wnt_signaling_pathway +
, http://dbpedia.org/resource/Jeanette_P._Schmidt +
, http://dbpedia.org/resource/Leonard_J._Schulman +
, http://dbpedia.org/resource/Minor_%28graph_theory%29 +
, http://dbpedia.org/resource/Derandomization +
, http://dbpedia.org/resource/Path_%28graph_theory%29 +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Category:Graph_algorithms +
, http://dbpedia.org/resource/Algorithmic_technique +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:%21 +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Sfrac +
, http://dbpedia.org/resource/Template:About +
, http://dbpedia.org/resource/Template:= +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Cite_journal +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_algorithms +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Color-coding?oldid=1115906832&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Color-coding +
|
| owl:sameAs |
http://yago-knowledge.org/resource/Color-coding +
, http://www.wikidata.org/entity/Q5148529 +
, https://global.dbpedia.org/id/4iE5f +
, http://ru.dbpedia.org/resource/%D0%A6%D0%B2%D0%B5%D1%82%D0%BE%D0%B2%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 +
, http://dbpedia.org/resource/Color-coding +
, http://sr.dbpedia.org/resource/Kodiranje_bojama +
, http://rdf.freebase.com/ns/m.05zp14w +
|
| rdf:type |
http://dbpedia.org/class/yago/Rule105846932 +
, http://dbpedia.org/class/yago/WikicatGraphAlgorithms +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Act100030358 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
, http://dbpedia.org/class/yago/Activity100407535 +
, http://dbpedia.org/class/yago/Algorithm105847438 +
, http://dbpedia.org/class/yago/Procedure101023820 +
, http://dbpedia.org/class/yago/Event100029378 +
|
| rdfs:comment |
In computer science and graph theory, the … 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.zed in 1994 by Noga Alon, , and Uri Zwick.
, Цветовое кодирование — , которая полезна д … Цветовое кодирование — , которая полезна для обнаружения . Например, она может быть использована для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но оно может быть без существенного увеличения времени работы. Цветовое кодирование также применяется для обнаружения циклов заданной длины и в более общем случае, к задаче поиска изоморфного подграфа (NP-полная задача), где оно даёт алгоритмы полиномиального времени, если искомый подграф имеет ограниченную древесную ширину.дграф имеет ограниченную древесную ширину.
|
| rdfs:label |
Color-coding
, Цветовое кодирование
|
