Summary: An experimental evaluation of a technique for improving the efficiency of depth-first search on graphs is presented. The technique, referred to as cycle checking, prevents the generation of duplicate nodes in the depth- first search of a graph by comparing each newly generated node to the nodes already on the search path. Although cycle checking can be applied to any depth-first type search, this paper focuses on its effect with the heuristic depth-first iterative deepening algorithm \(\text{IDA}^*\). Two types of cycle checking are compared, full cycle checking and parent cycle checking. Full cycle checking compares a new node to all nodes on the search path. Parent cycles checking merely compares a new node to the parent of the node being expanded. Both types of cycles checking are shown to improve the efficiency of \(\text{IDA}^*\) search in a grid search problem and a route planning problem. Simple guidelines are presented showing which types of cycle checking should be used on a given problem.