Page 159 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving UAVs 151

UAV

destination

Fig. 2. Find the minimum spanning tree

UAV

destination

Fig. 3. Double the edges in the minimum spanning tree to construct an Eulerian
graph

1.5-Approx Algorithm

Christofides in [3] reduced the approximation factor from 2 to 1.5 by coming up
a better way of constructing the Eulerian graph from the minimum spanning
tree. This gave rise to the following 1.5-Approx algorithm for SVP:

1. Find the Minimum Spanning Tree (MST) of the graph G. This step is
same as the step 1 presented in the 2-Approx algorithm (Fig. 2).
2. Find the minimum cost perfect matching (PM) on all the odd degree
vertices in the MST (Fig. 6).
3. Add all the edges in MST and PM to get an Eulerian graph (Fig. 7).
4. Find an Eulerian walk on this Eulerian graph (Fig. 8).