@Misc{pcp-instance-page,
author = {Frota, Y., Maculan, N., Noronha T.F., Ribeiro, C.C.},
title = {Instances for the partition Coloring Problem},
howpublished = {www.ic.uff.br/~celso/grupo/pcp.htm},
}
Let G=(V, E) be an undirected graph and Q be a partition of V in disjoint subsets of vertices. The partition coloring problem consists in finding a subset V' of V with exactly one vertex in each component of Q and such that the chromatic number of the subgraph induced by V' in G is minimum. This problem is NP-hard since it generalizes the vertex coloring problem.
The instances are separated in four classes as in [3]: (i) Random instances (Table 2), Graph coloring instances (Table 3), RWA instances associated with ring networks (Table 4), and RWA instances associated with the NSFnet network (Table 4). The format of the instance files is:
|V| |E| |Q|
for each vertex v:
Q[v]
for each edge (i,j):
i j
where Q[v] is the component of the partition Q that contains the vertex v.
Click here to download all instances.
[1] G. Li, R. Simha, The partition coloring problem and its application to wavelength routing and assignment, in: Proceedings of the First Workshop on Optical Networks, Dallas, 2000.
[2] T.F. Noronha, C.C. Ribeiro, Routing and wavelength assignment by partition coloring, European Journal of Operational Research, 171:797-810, 2006.
[3] Y. Frota, N. Maculan, T.F. Noronha, C.C. Ribeiro, A branch-and-cut algorithm for partition coloring, Networks, 2010, DOI: 10.1002/net.20365.
[4] E. A. Hoshino, C. C. de Souza, Y. Frota. A Branch-and-Price Approach for the Partition Coloring Problem, in: Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'09), Paris, 2009, pp. 187-190.
Last update: January 13, 2009