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 proceedingConference 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 languageEnglish (US)
    Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 17th Conference, 1997, Proceedings
    EditorsS. Ramesh, G. Sivakumar
    PublisherSpringer Verlag
    Pages37-53
    Number of pages17
    ISBN (Print)3540638768, 9783540638766
    DOIs
    StatePublished - 1997
    Event17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997 - Kharagpur, India
    Duration: Dec 18 1997Dec 20 1997

    Publication series

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

    Conference

    Conference17th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1997
    CountryIndia
    CityKharagpur
    Period12/18/9712/20/97

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Graph editing to bipartite interval graphs: Exact and asymptotic bounds'. Together they form a unique fingerprint.

    Cite this