Graph editing to bipartite interval graphs: Exact and asymptotic bounds

1. T. Andrae and M. Aigner. The total interval number of a graph. J. Comb. Theory, Series B, 46, 7–21, 1989.

   Article  Google Scholar 

2. F. Alizadeh, R.M. Karp, D.K. Weisser, G. Zweig, Physical Mapping of Chromosomes Using Unique Probes, J. Comp. Bio., 2(2):153–158, 1995.

   Google Scholar 

3. S. Arnborg, A. Proskurowski, Linear Time Algorithms for NP-Hard Problems Restricted to Partial k-Trees, Discrete Applied Mathematics, 23:11–24, 1989.

   Article  MATH  MathSciNet  Google Scholar 

4. H. Bodlaender. A tourist guide through treewidth. Manuscript, 1995.

   Google Scholar 

5. H. Bodlaender, M. Fellows, M. Hallet, T. Wareham and T. Warnow. The hardness of problems on thin colored graphs. Manuscript, 1995.

   Google Scholar 

6. H. Bodlaender, and B. de Fluiter. Intervalizing k-colored graphs. Proc. ICALP, 1995. Also, see http://www.cs.ruu.nl/~hansb/mypapers2.html for the journal version.

   Google Scholar 

7. H. Bodlaender, M. Fellows, and M. Hallet. Beyond the NP Completeness for problems of bounded width. Proc. STOC, 449–458, 1994.

   Google Scholar 

8. K. Booth and G. Leuker. Testing for the consecutive ones property, interval graphs and graph planarity using PQ algorithms. J. Comput. Syst. Sciences, 13, 335–379, 1976.

   MATH  Google Scholar 

9. N. G. Cooper(editor). The Human Genome Project — Deciphering the Blueprint of Heredity, University Science Books, Mill Valley, California, 1994.

   Google Scholar 

10. P. Cresenzi and V. Kann. The NP Completeness Compendium. See Section on Subgraphs and Supergraphs. http://www.nada.kth.se/viggo/problemlist/compendium.

    Google Scholar 

11. M. Farach, S. Kannan and T. Warnow. A robust model for constructing evolutionary trees. Proc. STOC, 1994.

    Google Scholar 

12. M. Fellows, M. Hallet and T. Wareham. DNA Physical Mapping: three ways difficult. Proc. First ESA, 157–168, 1993.

    Google Scholar 

13. P.W. Goldberg, M.C. Golumbic, H. Kaplan, R. Shamir, Four Strikes Against Physical Mapping of DNA, J. Comp. Bio., 2(1):139–152, 1995.

    Article  Google Scholar 

14. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of N P-Completeness, p 199–200. (Freeman, San Fransisco, CA, 1979)

    Google Scholar 

15. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

    MATH  Google Scholar 

16. M. Golumbic, H. Kaplan and R. Shamir On the complexity of DNA physical mapping. Adv. Appl. Math., 15:251–261, 1994.

    Article  MATH  MathSciNet  Google Scholar 

17. H. Kaplan and R. Shamir. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. To appear in SIAM. J. Computing, 1996.

    Google Scholar 

18. H. Kaplan and R. Shamir. Physical mapping and interval sandwich problems: Bounded degrees help. Manuscript, 1996.

    Google Scholar 

19. H. Kaplan, R. Shamir and R. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. Procs. of FOCS, 1994.

    Google Scholar 

20. R. Karp, Mapping the Genome: Some Combinatorial Problems Arising in Molecular Biology, 25th ACM STOC, 1993.

    Google Scholar 

21. P. Pevzner, M. Waterman. Open Combinatorial Problems in Computational Molecular Biology, Proceedings of the Third Israel Symposium on Theory of Computing and Systems, Jan 4–6, 1995, Tel Aviv, Israel.

    Google Scholar 

22. J. Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Reed Eds. Graph Theory and Computing, 183–217, Academic Press, NY, 1972.

    Google Scholar 

23. M. Waterman, J. R. Griggs, Interval Graphs and Maps of DNA, Bull. of Math. Biol., 48:189–195, 1986.

    Article  MATH  MathSciNet  Google Scholar 

24. M. Yannakakis. Computing the minimum fill-in is NP-Complete. SIAM J. ALg. Disc. Methods, 2, 1981.

    Google Scholar 

25. C. Wang. A subgraph problem from restriction maps of DNA chain. Journal of Computational Biology, 1995.

    Google Scholar 

Download references