Better lower and upper bounds for the minimum rainbow subgraph problem

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

POPA Alexandru

Rok publikování 2014
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1016/j.tcs.2014.05.008
Obor Informatika
Klíčová slova Approximation algorithms; Combinatorial problems; Minimum rainbow subgraph
Popis In this paper we study the minimum rainbow subgraph problem, motivated by applications in bioinformatics. The input of the problem consists of an undirected graph with n vertices where each edge is colored with one of the p possible colors. The goal is to find a subgraph of minimum order (i.e. minimum number of vertices) which has precisely one edge from each color class. In this paper we show a randomized max(root 2n, root Delta(1+root ln Delta/2))-approximation algorithm using LP rounding, where A is the maximum degree in the input graph. On the other hand we prove that there exists a constant c such that the minimum rainbow subgraph problem does not have a c In A-approximation, unless NP subset of DTIME(n(0(loglogn)))
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.