LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS
Vassilis Giakoumakis, Jean-Marie Vanherpe · International Journal of Foundations of Computer Science · 2003
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 P6-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.