| Identifikační kód | RIV/00216224:14330/14:00080116 |
|---|
| Název v anglickém jazyce | Better lower and upper bounds for the minimum rainbow subgraph problem |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2014 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 1 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Alexandru Popa (státní příslušnost: RO - Rumunsko, domácí tvůrce: A) |
|---|
| Popis výsledku v anglickém jazyce | 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 isthe 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))) |
|---|
| Klíčová slova oddělená středníkem | Approximation algorithms; Combinatorial problems; Minimum rainbow subgraph |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1016/j.tcs.2014.05.008 |
|---|