Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Graph editing to bipartite interval graphs: Exact and asymptotic bounds
| |
|
Graph editing to bipartite interval graphs: Exact and asymptotic bounds
K. Cirino1, S. Muthukrishnan2 , N. S. Narayanaswamy3 and H. Ramesh3 
| (1) |
Northeastern University, India |
| (2) |
Information Sciences Center, Bell Laboratories Innovations, Lucent Technologies, 07974 Murray Hill, NJ |
| (3) |
Dept. of Computer Science and Automation, Indian Institute of Science, 560012 Bangalore, India |
Abstract
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.
Work supported by DIMACS Special Year on Computational Biology.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|