This paper addresses a variant of the classical clique problem in which the edges of the graph are labeled. The problem consists of finding a clique as large as possible whose edge set contains at most b ∈ Z+ different labels. Moreover, in case of more feasible cliques of the same maximum size, we look for the one with the minimum number of labels. We study the time complexity of the problem, also in special cases, and we propose a mathematical programming approach for its solution by introducing two different formulations: the basic and the enforced. We experimentally evaluate the performance of the proposed approach on a set of benchmark instances (DIMACS) suitably adapted to the problem.
A Mathematical Programming Approach for the Maximum Labeled Clique Problem
CARRABS, FRANCESCO;CERULLI, Raffaele;
2014-01-01
Abstract
This paper addresses a variant of the classical clique problem in which the edges of the graph are labeled. The problem consists of finding a clique as large as possible whose edge set contains at most b ∈ Z+ different labels. Moreover, in case of more feasible cliques of the same maximum size, we look for the one with the minimum number of labels. We study the time complexity of the problem, also in special cases, and we propose a mathematical programming approach for its solution by introducing two different formulations: the basic and the enforced. We experimentally evaluate the performance of the proposed approach on a set of benchmark instances (DIMACS) suitably adapted to the problem.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
