E-viri
Recenzirano
Odprti dostop
-
Adamaszek, Anna; Popa, Alexandru
Algorithmica, 10/2015, Letnik: 73, Številka: 2Journal Article
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 G such that in the resulting graph G ′ all the connected components are colorful (i.e., any two vertices of the same color belong to different connected components). We want G ′ 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 N P -hard (assuming P ≠ N P ). Then, we show that the second problem is A P X -hard, thus proving and strengthening the conjecture of Zheng et al. that the problem is N P -hard. Finally, we show that the third problem does not admit polynomial-time approximation within a factor of | V | 1 / 14 - ϵ for any ϵ > 0 , assuming P ≠ N P (or within a factor of | V | 1 / 2 - ϵ , assuming Z P P ≠ N P ).
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.