A subgraph problem from restriction maps of DNA.
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.
Wang
C
C
Department of Mathematics, University of Louisville, KY 40292, USA.
D000465:Algorithms; D008432:Mathematical Computing; D015183:Restriction Mapping