About: Christofides algorithm

Property	Value
dbo:description	Algorithmus der Graphentheorie (de) алгоритм поиска приближённых решений задачи коммивояжёра для случаев (ru) algorithm that approximates solutions to the travellng salesman problem on a metric space, guaranteeing that its solutions will be within 1½ of the optimal solution length; discovered by Nicos Christofides in 1976 (en) algoritmo por proksimuma solvo de la kolportista problemo sur metrika spaco, kiu garantias ke la proksimuma solvo kuŝas en faktoro 1½ de la optimuma solvo; inventita de Nikos Ĥristofidis en 1976 (eo)
dbo:thumbnail	wiki-commons:Special:FilePath/Metrischer_Graph_mit_5_Knoten.svg?width=300
dbo:wikiPageExternalLink	https://xlinux.nist.gov/dads/HTML/christofides.html
dbo:wikiPageWikiLink	dbc:Spanning_tree dbr:Minimum_spanning_tree dbc:Graph_algorithms dbr:Metric_space dbc:Approximation_algorithms dbc:1976_in_computing dbr:Shortest_path_problem dbr:Multigraph dbr:Path_(graph_theory) dbr:Handshaking_lemma dbr:Algorithm dbr:Induced_subgraph dbr:Pseudocode dbr:Triangle_inequality dbr:Complete_graph dbr:Approximation_algorithm dbr:Degree_(graph_theory) dbc:Travelling_salesman_problem dbr:Travelling_salesman_problem dbr:Symposium_on_Theory_of_Computing dbr:Perfect_matching dbr:Nicos_Christofides dbr:Hamiltonian_circuit dbr:Eulerian_circuit dbr:Anatoliy_I._Serdyukov dbr:File:Christofides_MST.svg dbr:File:Christofides_Matching.svg dbr:File:Eulertour.svg dbr:File:Eulertour_bereinigt.svg dbr:File:G_V'.svg dbr:File:Metrischer_Graph_mit_5_Knoten.svg dbr:File:TuM.svg dbr:File:V'.svg
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Math dbt:CS1_config dbt:Mvar dbt:Langx dbt:Short_description
dct:subject	dbc:Spanning_tree dbc:Graph_algorithms dbc:Approximation_algorithms dbc:1976_in_computing dbc:Travelling_salesman_problem
gold:hypernym	dbr:Algorithm
rdf:type	dbo:Algorithm
rdfs:label	Christofides algorithm (en) Algorisme de Christofides (ca) Αλγόριθμος Χριστοφίδη (el) Algoritmo de Christofides (es) Algorithmus von Christofides (de) Algorithme de Christofides (fr) クリストフィードのアルゴリズム (ja) 크리스토피데스 알고리즘 (ko) Algorytm Christofidesa (pl) Algoritmo de Christofides (pt) Алгоритм Кристофидеса (ru) 克里斯托菲德斯算法 (zh)
owl:sameAs	yago-res:Christofides algorithm freebase:Christofides algorithm wikidata:Christofides algorithm dbpedia-de:Christofides algorithm dbpedia-fr:Christofides algorithm dbpedia-zh:Christofides algorithm dbpedia-ja:Christofides algorithm dbpedia-pt:Christofides algorithm dbpedia-es:Christofides algorithm dbpedia-fa:Christofides algorithm dbpedia-ru:Christofides algorithm dbpedia-vi:Christofides algorithm dbpedia-pl:Christofides algorithm dbpedia-ko:Christofides algorithm dbpedia-el:Christofides algorithm dbpedia-ca:Christofides algorithm dbpedia-sr:Christofides algorithm dbpedia-th:Christofides algorithm dbpedia-global:Christofides algorithm
prov:wasDerivedFrom	wikipedia-en:Christofides_algorithm?oldid=1294227389&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Christofides_MST.svg wiki-commons:Special:FilePath/Christofides_Matching.svg wiki-commons:Special:FilePath/Eulertour.svg wiki-commons:Special:FilePath/Eulertour_bereinigt.svg wiki-commons:Special:FilePath/G_V'.svg wiki-commons:Special:FilePath/Metrischer_Graph_mit_5_Knoten.svg wiki-commons:Special:FilePath/TuM.svg wiki-commons:Special:FilePath/V'.svg
foaf:isPrimaryTopicOf	wikipedia-en:Christofides_algorithm
is dbo:wikiPageRedirects of	dbr:Christofides_heuristic
is dbo:wikiPageWikiLink of	dbr:Minimum_spanning_tree dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Held–Karp_algorithm dbr:Galactic_algorithm dbr:Handshaking_lemma dbr:Cobham's_thesis dbr:Approximation_algorithm dbr:List_of_algorithms dbr:Travelling_salesman_problem dbr:Stacker_crane_problem dbr:Nicos_Christofides dbr:Christofides_heuristic
is foaf:primaryTopic of	wikipedia-en:Christofides_algorithm