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.
My Menu
Saved Items

Graph editing to bipartite interval graphs: Exact and asymptotic bounds

K. Cirino1, S. MuthukrishnanContact Information, N. S. NarayanaswamyContact Information and H. RameshContact Information

(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.

Contact Information S. Muthukrishnan
Email: muthu@research.bell-labs.com

Contact Information N. S. Narayanaswamy
Email: swamy@csa.iisc.ernet.in

Contact Information H. Ramesh
Email: ramesh@csa.iisc.ernet.in
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)