Algorithmic approaches for the minimum rainbow subgraph problem


Algorithmic approaches for the minimum rainbow subgraph problem

Koch, M.; Matos Camacho, S.; Schiermeyer, I.

We consider the Minimum Rainbow Subgraph problem (MRS): Given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of minimum order and with p edges such that each colour occurs exactly once. This problem is APX-hard. In this paper we will show that the Greedy algorithm for the MRS problem has an approximation ratio of Δ/2 + (lnΔ+1)/2 for graphs with maximum degree Δ. If the average degree d of a minimum rainbow subgraph is known, then the approximation ratio is d/2 + (ln[d]+1)/2.

Keywords: 10.1016/j.endm.2011.10.028

Permalink: https://www.hzdr.de/publications/Publ-20516
Publ.-Id: 20516