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%2F15%3A00087420" target="_blank" >RIV/00216224:14330/15:00087420 - isvavai.cz</a>
Result on the web
<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>
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 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 ).
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
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
Name of the periodical
ALGORITHMICA
ISSN
0178-4617
e-ISSN
—
Volume of the periodical
73
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
18
Pages from-to
371-388
UT code for WoS article
000360668100005
EID of the result in the Scopus database
—