Graph editing to bipartite interval graphs: Exact and asymptotic bounds.

Graph editing problems deal with the complexity of transforming a given input graph G from class Q to any graph H in the target class H by adding and deleting edges. Motivated by a physical mapping scenario in Computational Biology, we consider graph editing to the class of bipartite interval graphs (BIGs). We prove asymptotic and exact bounds on the minimum number of editions needed to convert a graph into a BIG. [ABSTRACT FROM AUTHOR]