(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.
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 28 October 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "Christofides algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 28 October 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/christofides.html