Carving-Decomposition Based Algorithms for the Maximum Path Coloring Problem

Given a set P of paths in a graph G and k colors, the Maximum Path Coloring (Max-PC) problem is to find a maximum subset of P and assign a color to each path of the subset such that the paths with the same color are edge dis-joint. The Max-PC problem is an abstract model for many important routing problems including the all-optical routing. The authors give a carving-decomposition based exact algorithm for the Max-PC problem. A carving-decomposition of G is a system of edge-cut sets which decomposes G into sub-graphs with each vertex of G a minimal sub-graph.