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