Algorithmic and Hardness Results for the Colorful Components Problems
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Algorithmic and Hardness Results for the Colorful Components Problems
Original language description
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).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Employment of Newly Graduated Doctors of Science for Scientific Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
11th Latin American Theoretical Informatics Symposium, LATIN 2014
ISBN
9783642544224
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
683-694
Publisher name
Springer
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000342804300059