| Identifikační kód | RIV/00216224:14330/15:00087420 |
|---|
| Název v anglickém jazyce | Algorithmic and Hardness Results for the Colorful Components Problems |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| 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 | 2 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Anna Adamaszek (státní příslušnost: PL - Polská republika)
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 investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges from an undirected vertex-colored graph such that in the resulting graph allthe connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want to optimize an objective function, the selection of this function being specific to each problem in the framework. We analyze three objective functions, and thus, three different problems, which are believed to be relevant for the biological applications: minimizing the number of singleton vertices, maximizing the number of edges in the transitive closure, and minimizing the number of connected components. Our main result is a polynomial-time algorithm for the first problem. This result disproves the conjecture of Zheng et al. that the problem is -hard (assuming ). |
|---|
| Klíčová slova oddělená středníkem | Colorful components; Graph coloring; Exact polynomial-time algorithms; Hardness of approximation |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/s00453-014-9926-0 |
|---|