(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.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 28 October 2008.

HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:

Paul E. Black, "Christofides algorithm", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 28 October 2008. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/christofides.html