Vertex-weighted maximum clique problem (VWMCP)

Catalogue of combinatorial problems · Clique problems · Catalogue (PDF)

Definition 1: Vertex-weighted maximum clique problem

1. Given a graph \(G\) and a vertex-weight vector \(\vet{w}\), the vertex-weighted maximum clique problem (VWMCP) asks to find a clique \(K\) of \(G\) with maximum total vertex weight \(w(K)\).

2. Given a graph \(G\) and an edge-weight vector \(\vet{r}\), the edge-weighted maximum clique problem (EWMCP) asks to find a clique \(K\) of \(G\) with maximum total edge weight \(r(K)\).

What the course does on this problem

Technique	Where
Definition	Ch. 5 «Clique problems»
Formulations	Ch. 12 «Formulations of clique problems»
Exercises	Exercise 5.5; Exercise 12.7