Graph editing to bipartite interval graphs: Exact and asymptotic bounds

K. Cirino; S. Muthukrishnan; N. S. Narayanaswamy; H. Ramesh

doi:10.1007/bfb0058021

Graph editing to bipartite interval graphs: Exact and asymptotic bounds

K. Cirino, S. Muthukrishnan, N. S. Narayanaswamy, H. Ramesh

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Graph editing problems deal with the complexity of transforming a given input graph G from class g 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.

Original language	English (US)
Title of host publication	Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings
Editors	S. Ramesh, G. Sivakumar
Publisher	Springer Verlag
Pages	37-53
Number of pages	17
ISBN (Print)	3540638768, 9783540638766
DOIs	https://doi.org/10.1007/bfb0058021
State	Published - 1997
Event	17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997 - Kharagpur, India Duration: Dec 18 1997 → Dec 20 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1346
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997
Country/Territory	India
City	Kharagpur
Period	12/18/97 → 12/20/97

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0058021

Cite this

Cirino, K., Muthukrishnan, S., Narayanaswamy, N. S., & Ramesh, H. (1997). Graph editing to bipartite interval graphs: Exact and asymptotic bounds. In S. Ramesh, & G. Sivakumar (Eds.), Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings (pp. 37-53). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1346). Springer Verlag. https://doi.org/10.1007/bfb0058021

Graph editing to bipartite interval graphs: Exact and asymptotic bounds. / Cirino, K.; Muthukrishnan, S.; Narayanaswamy, N. S. et al.
Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings. ed. / S. Ramesh; G. Sivakumar. Springer Verlag, 1997. p. 37-53 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1346).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cirino, K, Muthukrishnan, S, Narayanaswamy, NS & Ramesh, H 1997, Graph editing to bipartite interval graphs: Exact and asymptotic bounds. in S Ramesh & G Sivakumar (eds), Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1346, Springer Verlag, pp. 37-53, 17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997, Kharagpur, India, 12/18/97. https://doi.org/10.1007/bfb0058021

Cirino K, Muthukrishnan S, Narayanaswamy NS, Ramesh H. Graph editing to bipartite interval graphs: Exact and asymptotic bounds. In Ramesh S, Sivakumar G, editors, Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings. Springer Verlag. 1997. p. 37-53. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0058021

Cirino, K. ; Muthukrishnan, S. ; Narayanaswamy, N. S. et al. / Graph editing to bipartite interval graphs : Exact and asymptotic bounds. Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings. editor / S. Ramesh ; G. Sivakumar. Springer Verlag, 1997. pp. 37-53 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6df87e2ca09649bfa60d7d63e370b7db,

title = "Graph editing to bipartite interval graphs: Exact and asymptotic bounds",

abstract = "Graph editing problems deal with the complexity of transforming a given input graph G from class g 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.",

author = "K. Cirino and S. Muthukrishnan and Narayanaswamy, {N. S.} and H. Ramesh",

note = "Publisher Copyright: {\textcopyright} 1997, Springer Verlag.; 17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997 ; Conference date: 18-12-1997 Through 20-12-1997",

year = "1997",

doi = "10.1007/bfb0058021",

language = "English (US)",

isbn = "3540638768",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "37--53",

editor = "S. Ramesh and G. Sivakumar",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings",

}

TY - GEN

T1 - Graph editing to bipartite interval graphs

T2 - 17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997

AU - Cirino, K.

AU - Muthukrishnan, S.

AU - Narayanaswamy, N. S.

AU - Ramesh, H.

PY - 1997

Y1 - 1997

N2 - Graph editing problems deal with the complexity of transforming a given input graph G from class g 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.

AB - Graph editing problems deal with the complexity of transforming a given input graph G from class g 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.

UR - http://www.scopus.com/inward/record.url?scp=84949197136&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949197136&partnerID=8YFLogxK

U2 - 10.1007/bfb0058021

DO - 10.1007/bfb0058021

M3 - Conference contribution

AN - SCOPUS:84949197136

SN - 3540638768

SN - 9783540638766

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 37

EP - 53

BT - Foundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings

A2 - Ramesh, S.

A2 - Sivakumar, G.

PB - Springer Verlag

Y2 - 18 December 1997 through 20 December 1997

ER -

Graph editing to bipartite interval graphs: Exact and asymptotic bounds

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this