Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

A subgraph problem from restriction maps of DNA

C Wang1

  • 1Department of Mathematics, University of Louisville, KY 40292, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1994
PubMed
Summary

This study proves that finding the minimum edge removals to create interval graphs is NP-complete. A polynomial algorithm is presented for finding maximum interval subgraphs in trees, enabling heuristic development.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

The platelet-derived growth factor alpha-receptor is encoded by a growth-arrest-specific (gas) gene.

Proceedings of the National Academy of Sciences of the United States of America·1996
Same author

Data from men in greater Seattle area reveals no downward trend in semen quality: further evidence that deterioration of semen quality is not geographically uniform.

Fertility and sterility·1996
Same author

Microsatellite instability in transitional cell carcinoma of the urinary tract and its relationship to clinicopathological variables and smoking.

International journal of cancer·1996
Same author

Sexual dimorphism of cardiovascular responses to early blockade of bradykinin receptors.

Hypertension (Dallas, Tex. : 1979)·1996
Same author

Rate-determining steps for tyrosine phosphorylation by the kinase domain of v-fps.

Biochemistry·1996
Same author

Cell-type-specific expression of the platelet-derived growth factor alpha receptor: a role for GATA-binding protein.

Molecular and cellular biology·1996

Area of Science:

  • Graph theory
  • Computational complexity
  • Bioinformatics

Background:

  • The problem of converting bipartite graphs to interval graphs relates to DNA restriction mapping.
  • Determining the minimum edge removals for this conversion is a key challenge.

Purpose of the Study:

  • To analyze the computational complexity of converting bipartite graphs to interval graphs.
  • To develop an efficient algorithm for finding interval subgraphs in trees.

Main Methods:

  • Complexity analysis to determine the problem's NP-completeness.
  • Design of a polynomial-time algorithm for finding edge-maximum interval subgraphs on trees.

Main Results:

  • The problem of minimum edge removals to achieve interval graphs is proven to be NP-complete.
  • A polynomial algorithm is developed for finding maximum interval subgraphs in trees.

Conclusions:

  • The NP-completeness suggests the difficulty of the general problem.
  • The developed algorithm provides a foundation for heuristic approaches to interval graph approximation.

Related Experiment Videos