(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 by skipping vertices already seen. (2) An algorithm to find the chromatic number of a graph.
Also known as Christofides heuristic.
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
A PDF document explaining the algorithm with proof of guarantee.
(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 E. Black.
Entry modified 27 December 2005.
HTML page formatted Mon Sep 11 09:46:01 2006.
Cite this as:
Paul E. Black, "Christofides algorithm", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 27 December 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/christofides.html
