Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
gptkb:approximation_algorithm |
| gptkbp:appliesTo |
gptkb:metric_TSP
|
| gptkbp:approximationRatio |
1.5
|
| gptkbp:complexity |
polynomial time
|
| gptkbp:field |
gptkb:theoretical_computer_science
combinatorial optimization operations research |
| gptkbp:introducedIn |
1976
|
| gptkbp:namedAfter |
Nicos Christofides
|
| gptkbp:solvedBy |
gptkb:Traveling_Salesman_Problem
|
| gptkbp:step |
shortcut repeated vertices to form Hamiltonian circuit
combine edges to form Eulerian multigraph construct minimum spanning tree find Eulerian circuit find odd degree vertices find minimum weight perfect matching on odd degree vertices |
| gptkbp:uses |
gptkb:Eulerian_circuit
minimum spanning tree minimum weight perfect matching |
| gptkbp:bfsParent |
gptkb:Traveling_salesman_problem
gptkb:traveling_salesman_problem |
| gptkbp:bfsLayer |
7
|
| https://www.w3.org/2000/01/rdf-schema#label |
Christofides algorithm
|