We then have to develop fast and easily implementable heuristic algorithms. Very often, the problem that we encounter has a fast, possibly even linear time, algorithm but it is very difficult to implement so that this time bound is achieved. Very often this occurs because complicated data structures have been used. Our goal then is to find an algorithm that achieves the same time bound but is easy to implement. Such a graph can be represented by the intersection model of intervals of a line.
Interval graphs play a fundamental role in the genome mapping problem.
Over the following 20 years, other linear time algorithms have been developed, but these algorithms also required considerable effort to implement. The general LBFS allows arbitrary choice when a set of vertices are tied as to which should be chosen next. Our algorithm uses two variations of LBFS, each giving a different method for breaking ties. Although I typically don't work on practical problems, my students often do. It was shown that the patch cost very little to run but would often identify very problematic areas in the input graph that would have to be treated carefully.