On the last few years several problems have been studied on a particular class of graphs, where each edge has a label (color) assigned to it. Real applications for this class of problems arise in fields such as telecommunication or multimodal transport networks (edges of the same color can model transportation lines of the same type, or connections belonging to the same company). Moreover, the edge-labeled graphs can be of interest whenever we need some measure of homogeneity (or heterogeneity) regarding the edges in the solution we are looking for. In this context we focalize our attention on the "monochromatic set partitioning problem" (MSP). Let G=(V,E) be an edge-colored graph. A sub-graph H of G is said to be monochromatic if all the edges of H have the same color and multicolored if no two edges of H have the same color. A feasible solution for the MSP is a partitioning of G in monochromatic sub-graph. We look for a feasible solution containing the minimum number of such monochromatic sub-graph. In our work we first prove the complexity of this problem. Then we propose a mathematical formulation and a polynomial case. Finally we present a meta-heuristic approach to solve the problem and show some preliminary computational results.
The monochromatic set partitioning problem.Presentato al convegno Airo 2010, 07-10 Settembre 2010, Villa San Giovanni (RC).
CERULLI, Raffaele;CARRABS, FRANCESCO;
2010-01-01
Abstract
On the last few years several problems have been studied on a particular class of graphs, where each edge has a label (color) assigned to it. Real applications for this class of problems arise in fields such as telecommunication or multimodal transport networks (edges of the same color can model transportation lines of the same type, or connections belonging to the same company). Moreover, the edge-labeled graphs can be of interest whenever we need some measure of homogeneity (or heterogeneity) regarding the edges in the solution we are looking for. In this context we focalize our attention on the "monochromatic set partitioning problem" (MSP). Let G=(V,E) be an edge-colored graph. A sub-graph H of G is said to be monochromatic if all the edges of H have the same color and multicolored if no two edges of H have the same color. A feasible solution for the MSP is a partitioning of G in monochromatic sub-graph. We look for a feasible solution containing the minimum number of such monochromatic sub-graph. In our work we first prove the complexity of this problem. Then we propose a mathematical formulation and a polynomial case. Finally we present a meta-heuristic approach to solve the problem and show some preliminary computational results.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
