Wang C
Department of Mathematics, University of Louisville, KY 40292, USA.
J Comput Biol. 1994 Fall;1(3):227-34. doi: 10.1089/cmb.1994.1.227.
Computing the minimum number of edge removals needed to convert a bipartite graph into an interval graph was proposed by Waterman and Griggs in the study of restriction maps of DNA. We show that this problem is N P-complete and we give a polynomial algorithm that finds an edge-maximum interval subgraph for trees. Then various heuristics can be devised using this algorithm.
沃特曼和格里格斯在对DNA限制图谱的研究中提出了计算将二分图转换为区间图所需移除的最少边数的问题。我们证明了这个问题是NP完全问题，并给出了一种多项式算法，该算法能找到树的边最大区间子图。然后可以使用该算法设计各种启发式算法。
