Discrete Mathematics & Theoretical Computer Science 
Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edgecolored graph $G=(V,E)$, a subgraph $H$ is said to be <i>monochromatic</i> if all its edges have the same color, and called <i>multicolored</i> if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APXhard on monochromaticdiamondfree graphs, and APXcomplete on monochromaticdiamondfree graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NPcomplete, even if the input graph $G$ is trianglefree. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromaticdiamondfree graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $V(G)+1$.
Source : ScholeXplorer
IsRelatedTo DOI 10.1007/9783540748397_31 Source : ScholeXplorer IsRelatedTo DOI 10.1007/s0045300892614
