Další formáty:
BibTeX
LaTeX
RIS
@article{1298542, author = {Popa, Alexandru}, article_number = {C}, doi = {http://dx.doi.org/10.1016/j.tcs.2014.05.008}, keywords = {Approximation algorithms; Combinatorial problems; Minimum rainbow subgraph}, language = {eng}, issn = {0304-3975}, journal = {Theoretical Computer Science}, title = {Better lower and upper bounds for the minimum rainbow subgraph problem}, volume = {543}, year = {2014} }
TY - JOUR ID - 1298542 AU - Popa, Alexandru PY - 2014 TI - Better lower and upper bounds for the minimum rainbow subgraph problem JF - Theoretical Computer Science VL - 543 IS - C SP - 1-8 EP - 1-8 PB - North Holland SN - 03043975 KW - Approximation algorithms KW - Combinatorial problems KW - Minimum rainbow subgraph N2 - 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))) ER -
POPA, Alexandru. Better lower and upper bounds for the minimum rainbow subgraph problem. \textit{Theoretical Computer Science}. North Holland, 2014, roč.~543, C, s.~1-8. ISSN~0304-3975. Dostupné z: https://dx.doi.org/10.1016/j.tcs.2014.05.008.
|