Dovetailing (computer science)

Dovetailing in algorithm design, is a technique that interweaves different computations, performing them essentially simultaneously. Algorithms that use dovetailing are sometimes referred to as dovetailers.

Consider a tree that potentially contains a path of infinite length: if a depth-first search is performed in this environment, the search may move down an infinite path and never return, potentially leaving part of the tree unexplored. However, if a breadth-first search is used, the existence of an infinite path is no longer a problem: each node is visited in a branching manner according to its distance from the root, so an infinite path will only impact the part of the search travelling down that path.