Algorithmic and Hardness Results for the Colorful Components Problems
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00080117" target="_blank" >RIV/00216224:14330/14:00080117 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-54423-1_59" target="_blank" >http://dx.doi.org/10.1007/978-3-642-54423-1_59</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-54423-1_59" target="_blank" >10.1007/978-3-642-54423-1_59</a>
Alternativní jazyky
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 G such that in the resulting graph C' 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 NP-hard (assuming P not equal NP).
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 G such that in the resulting graph C' 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 NP-hard (assuming P not equal NP).
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2014
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
11th Latin American Theoretical Informatics Symposium, LATIN 2014
ISBN
9783642544224
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
12
Strana od-do
683-694
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Berlin
Datum konání akce
1. 1. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000342804300059