Algorithmic and Hardness Results for the Colorful Components Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00087420" target="_blank" >RIV/00216224:14330/15:00087420 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00453-014-9926-0" target="_blank" >http://dx.doi.org/10.1007/s00453-014-9926-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-014-9926-0" target="_blank" >10.1007/s00453-014-9926-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Algorithmic and Hardness Results for the Colorful Components Problems

Popis výsledku v původní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 ).

Název v anglickém jazyce

Algorithmic and Hardness Results for the Colorful Components Problems

Popis výsledku anglicky

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 ).

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ALGORITHMICA

ISSN

0178-4617

e-ISSN

—

Svazek periodika

73

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

371-388

Kód UT WoS článku

000360668100005

EID výsledku v databázi Scopus

—