Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
approximation algorithm |
| gptkbp:appliesTo |
gptkb:metric_TSP
|
| gptkbp:approximationRatio |
1.5
|
| gptkbp:complexity |
polynomial time
|
| gptkbp:field |
combinatorial optimization
operations research theoretical computer science |
| https://www.w3.org/2000/01/rdf-schema#label |
Christofides algorithm
|
| 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 |
6
|