TY - GEN

T1 - An optimisation algorithm for maximum independent set with applications in map labelling

AU - Verweij, B.

AU - Aardal, K.I.

PY - 1999

Y1 - 1999

N2 - We consider the following map labelling problem: given distinct points p 1, p 2,...,p n in the plane, find a set of pairwise disjoint axis-parallel squares Q 1,Q 2,...,Q n where p i is a corner of Q i . This problem reduces to that of finding a maximum independent set in a graph.
We present a branch and cut algorithm for finding maximum independent sets and apply it to independent set instances arising from map labelling. The algorithm uses a new technique for setting variables in the branch and bound tree that implicitly exploits the Euclidean nature of the independent set problems arising from map labelling. Computational experiments show that this technique contributes to controlling the size of the branch and bound tree. We also present a novel variant of the algorithm for generating violated odd-hole inequalities. Using our algorithm we can find provably optimal solutions for map labelling instances with up to 950 cities within modest computing time, a considerable improvement over the results reported on in the literature.

AB - We consider the following map labelling problem: given distinct points p 1, p 2,...,p n in the plane, find a set of pairwise disjoint axis-parallel squares Q 1,Q 2,...,Q n where p i is a corner of Q i . This problem reduces to that of finding a maximum independent set in a graph.
We present a branch and cut algorithm for finding maximum independent sets and apply it to independent set instances arising from map labelling. The algorithm uses a new technique for setting variables in the branch and bound tree that implicitly exploits the Euclidean nature of the independent set problems arising from map labelling. Computational experiments show that this technique contributes to controlling the size of the branch and bound tree. We also present a novel variant of the algorithm for generating violated odd-hole inequalities. Using our algorithm we can find provably optimal solutions for map labelling instances with up to 950 cities within modest computing time, a considerable improvement over the results reported on in the literature.

U2 - 10.1007/3-540-48481-7_37

DO - 10.1007/3-540-48481-7_37

M3 - Conference contribution

SN - 3-540-66251-0

T3 - Lecture Notes in Computer Science

SP - 426

EP - 437

BT - Algorithms - ESA'99 : Proceedings 7th annual European symposium, Prague, Czech Republic, july 16-18, 1999

A2 - Nesetril, J.

PB - Springer

ER -