Algorithms for weakly triangulated graphs

The authors present improved algorithms for the recognition and the weighted versions of the optimization problems for the class of weakly triangulated graphs. In particular, they improve the complexity of the recognition problem from to , the complexity of finding maximum weighted clique and minimum weighted coloring from to , and the complexity of finding maximum weighted independent set and minimum weighted clique cover from to .