Graph decomposition based algorithms for maximum path coloring and connected subgraph problems
Mehwish Bashir · Summit (Simon Fraser University) · 2012
Many application problems in networks can be modeled as optimization problems in a graph G.For example, the maximum path coloring (Max-PC) problem, described next is an abstract model for many routing problems: Given a set P of paths in G and k colors, 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-disjoint.One approach for solving an optimization problem in G is to decompose G into subgraphs, find partial solutions in each subgraph and combine the partial solutions into a solution of the problem.A carving-decomposition (branch-decomposition) of G is a system of edge-cuts (vertex-cuts) which decomposes G into subgraphs with each edge (vertex) a minimal subgraph.We give a carving-decomposition based exact algorithm and 1.58-approximation algorithm for the Max-PC problem.Let L be the maximum number of paths in P on any edge of G and let γ be the maximum cardinality of any edge-cut in a given carving-decomposition.Our exact algorithm and approximation algorithm run in O((L + 1) 1.5kγ n 2 ) and O((L + 1) 1.5γ kn 2 ) time, respectively.Our computational study shows that the exact algorithm can solve the Max-PC problem for small k and γ in a practical time and the approximation algorithm gives solutions close to optimal ones for practical values of k and L, and small γ.We also conduct a computational study on a branch-decomposition based exact algorithm for the maximum edge degreebounded connected subgraph (MEDBCS) problem.Our result shows that the MEDBCS problem of vertex-degree bounded by 3 can be solved for graphs with small branchwidth in a practical time.