Article ID Journal Published Year Pages File Type
10332013 Information Processing Letters 2011 5 Pages PDF
Abstract
► Polynomial time approximation to the Minimum rainbow subgraph and Minimum primer set in terms of maximum degree of a graph. ► Minimum rainbow subgraph problem is NP-hard and APX-hard even for graphs with maximum degree 2. ► Exact algorithm to the Minimum rainbow subgraph problem. ► Fixed-parameter tractability for the Minimum rainbow subgraph problem.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Improved approximation bounds for the minimum rainbow subgraph problem
Authors
, ,