Approximation algorithms for the minimum rainbow subgraph problem
Approximation algorithms for the minimum rainbow subgraph problem
Matos Camacho, S.; Schiermeyer, I.; Tusa, Z.
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 G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of View the MathML source for Δ≥2.
Keywords: Edge colouring; Minimum rainbow subgraph; Approximation algorithm
-
Discrete Mathematics 310(2010)20, 2666-2670
DOI: 10.1016/j.disc.2010.03.032
Cited 9 times in Scopus
Permalink: https://www.hzdr.de/publications/Publ-20515