A Polynomial Time Recognition Algorithm for Totally Bounded Bitolerance Digraphs
Randy Shull, Wellesley College

The classes of interval digraphs and bounded bitolerance digraphs represent two important directed analogues to the well-known class of interval graphs. Until recently, neither class was known to have an efficient recognition algorithm. In 1997, Haiko M\"{u}ller published a polynomial-time recognition algorithm for interval digraphs. In this talk, modify M\"{u}ller's algorithm in order to recognize the class of totally bounded bitolerance digraphs in polynomial time. In the case that the digraph is totally bounded bitolerance, the algorithm produces a representation.