In [7] was introduced a new decomposition scheme for bipartite graphs that was called canonical decomposition. Weak- bisplit 9raphs 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{sub}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.
展开▼
