## Efficient algorithms for some packing and covering problems on graphs |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

SURVEY OF VERTEX PACKING AND RELATED PROBLEMS | 12 |

AN ALGORITHM FOR THE MAXIMUM WEIGHTED VERTEX | 23 |

ALGORITHMS FOR MAXIMUM CLIQUES MINIMUM CLIQUE COVERS | 39 |

1 other sections not shown

### Common terms and phrases

adjacent articulation vertex augmenting path bipartite graphs black vertices block of G Chapter chordal graphs circular arc graphs claw claw-free graphs claw-free perfect graphs clique cover problem clique in G clique problem comparability graphs complement graph Consider edge coloring efficient algorithms exists an augmenting find a maximum Four Problems G contains G is perfect graph G Hence holes or odd independent set induced subgraph intersection graph Lemma length paths Let G line graphs linear programming maximum clique maximum packing maximum vertex packing maximum weighted packing minimum cardinality minimum clique cover NP-complete NP-hard odd anti-holes odd cycle odd holes packing on G partition polynomial algorithm problem on claw-free problem on graphs Proposition 4.4 recursive rithm set of vertices shown in Figure simple graph solved SPGC is true subgraph of G successor Suppose triangle vertex cover vertex of G vertex packing problem vertex set white vertices wt(u wt(v x,y e