(algorithm)
Definition: (1) A heuristic algorithm to find a near-optimal solution to the traveling salesman problem. Step 1: find a minimum spanning tree T. Step 2: find a perfect matching M among vertices with odd degree. Step 3: combine the edges of M and T to make a multigraph G. Step 4: find an Euler cycle in G. Step 5: Turn the Euler cycle into a Hamiltonian cycle by skipping vertices already seen. (2) An algorithm to find the chromatic number of a graph.
Generalization (I am a kind of ...)
heuristic.
Aggregate child (... is a part of or used in me.)
minimum spanning tree, perfect matching, multigraph, Euler cycle.
Author: PEB
(1) Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
Also CMU Tech. Report CS-93-13, 1976. Also Sympos. on New Directions and Recent Results in Algorithms and Complexity, J. F. Traub ed., page 441, Academic Press, New York, NY, 1976.
(2) Nicos Christofides, An algorithm for the chromatic number of a graph, Computer J., 14(1):38-39, February 1971.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 24 November 2020.
HTML page formatted Tue Nov 24 09:46:12 2020.
Cite this as:
Paul E. Black, "Christofides algorithm", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 24 November 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/christofides.html