Theory and Algorithms Commons^™

A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu

Computer Science Faculty Publications

The P₄-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P₄-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. A remarkable property of P₄-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P₄-reducible graphs and to construct their corresponding tree representation.