On the approximability of the exemplar adjacency number problem for genomes with gene repetitions

DOI10.1016/j.tcs.2014.07.011zbMath1417.68050MaRDI QIDQ401311

Guo-Hui Lin, Jinhui Xu, Boting Yang, Binhai Zhu, Zhixiang Chen, Weitian Tong, Randy Goebel, Bin Fu, Zhiyu Zhao

Publication date: 26 August 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.011

zbMATH Keywords

breakpoint; approximation algorithm; NP-hardness; adjacency; genome comparison

Mathematics Subject Classification ID

05C90: Applications of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

92D10: Genetics and epigenetics

68W25: Approximation algorithms