ALGORITHMS FOR WEAKLY TRIANGULATED GRAPHS

We present improved algorithms for the recognition and the weighted ve rsions of the optimization problems for the class of weakly triangulat ed graphs. In particular, we improve the complexity of the recognition problem from O(n(4.376)) to O (mn(2)), the complexity of finding maxi mum weighted clique and minimum weighted coloring from O(n(5)) to O(n( 4)), and the complexity of finding maximum weighted independent set an d minimum weighted clique cover from O(mn(3)) to O(n(4)).