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

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