A simple paradigm for graph recognition: application to cographs and distance hereditary graphs

An easy way for graph recognition algorithms is to use a two-step process: first, compute a characteristic feature as if the graph belongs to that cla ss; second, check whether the computed feature really defines the input gra ph. Although in some cases the two steps can be merged, separating them may yield new and much more easily understood algorithms. In this paper we app ly that paradigm to the cograph and distance hereditary graph recognition p roblems. (C) 2001 Elsevier Science BN. All rights reserved.