Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648882 | Discrete Mathematics | 2010 | 5 Pages |
Abstract
We consider the minimum rainbow subgraph problem (MRS): given a graph GG, whose edges are coloured with pp colours. Find a subgraph F⊆GF⊆G of GG of minimum order and with pp edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G)Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G)Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of 56Δ for Δ≥2Δ≥2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stephan Matos Camacho, Ingo Schiermeyer, Zsolt Tuza,