LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P₆-FREE GRAPHS

Abstract

In [7] was introduced a new decomposition scheme for bipartite graphs that was called canonical decomposition. Weak-bisplit graphs are totally decomposable following this decomposition. We give here linear time algorithms for the recognition of weak-bisplit graphs as well as for two subclasses of this class, the P 6 -free bipartite graphs and the bi-cographs. Our algorithms extends the technics developped in [2] for cographs's recognition. We conclude by presenting efficient solutions for some optimization problems when dealing with weak-bisplit graphs.