Better lower and upper bounds for the minimum rainbow subgraph problem

POPA, Alexandru. Better lower and upper bounds for the minimum rainbow subgraph problem. Theoretical Computer Science. North Holland, 2014, roč. 543, C, s. 1-8. ISSN 0304-3975. Dostupné z: https://dx.doi.org/10.1016/j.tcs.2014.05.008.

Základní údaje

• Originální název: Better lower and upper bounds for the minimum rainbow subgraph problem
• Autoři: POPA, Alexandru (642 Rumunsko, garant, domácí).
• Vydání: Theoretical Computer Science, North Holland, 2014, 0304-3975.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Nizozemské království
• Utajení: není předmětem státního či obchodního tajemství
• Impakt faktor: Impact factor: 0.657
• Kód RIV: RIV/00216224:14330/14:00080116
• Organizační jednotka: Fakulta informatiky
• Doi: http://dx.doi.org/10.1016/j.tcs.2014.05.008
• UT WoS: 000339702600001
• Klíčová slova anglicky: Approximation algorithms; Combinatorial problems; Minimum rainbow subgraph

Anotace

In this paper we study the minimum rainbow subgraph problem, motivated by applications in bioinformatics. The input of the problem consists of an undirected graph with n vertices where each edge is colored with one of the p possible colors. The goal is to find a subgraph of minimum order (i.e. minimum number of vertices) which has precisely one edge from each color class. In this paper we show a randomized max(root 2n, root Delta(1+root ln Delta/2))-approximation algorithm using LP rounding, where A is the maximum degree in the input graph. On the other hand we prove that there exists a constant c such that the minimum rainbow subgraph problem does not have a c In A-approximation, unless NP subset of DTIME(n(0(loglogn)))

Návaznosti

• EE2.3.30.0009, projekt VaV: Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci