  We introduce the minimum labelling spanning bi-connected subgraph problem
(MLSBP) replacing connectivity by bi-connectivity in the well known minimum
labelling spanning tree problem (MLSTP). A graph is bi-connected if, for every
two vertices, there are, at least, two vertex-disjoint paths joining them. The
problem consists in finding the spanning bi-connected subgraph or block with
minimum set of labels. We adapt the exact method of the MLSTP to solve the
MLSTB and the basic greedy constructive heuristic, the maximum vertex covering
algorithm (MVCA). This proce- dure is a basic component in the application of
metaheuristics to solve the problem.
