Weighted parameters in \((P_5,\overline {P_5})\)-free graphs (Q1382285): Difference between revisions

Let \(G\) be a graph with \(n\) vertices and \(m\) edges. The authors give \(O(n(m+n))\) algorithms for finding a maximum weighted clique and an approximate weighted colouring in a \((P_5, \overline {P_5})\)-free graph. They also obtain an \(O(m+n)\) algorithm for finding a minimum weighted transversal of the \(C_5\) in a \((P_5, \overline {P_5})\)-free graph.