Interval graphs and maps of DNA

DOI10.1007/BF02460022MaRDI QIDQ1071684zbMATH OpenOpenAlexWikidataFDO

Authors Michael S. Waterman, J. Griggs

Publication date 1986

Published in Bulletin of Mathematical Biology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02460022

zbMATH Keywords

algorithmCircular restriction mapsinterval graphsrepresentation of DNArestriction maps

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Physiological, cellular and medical topics (92Cxx)

Recommendations

• On probe interval graphs
• Tree loop graphs
• Tagged probe interval graphs
• scientific article; zbMATH DE number 2119749
• On intervalizing k-colored graphs for DNA physical mapping

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Incidence matrices with the consecutive 1’s property
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(24)

• Mapping DNA by stochastic relaxation
• Multiple solutions of DNA restriction mapping problems
• Convex and isometric domination of (weak) dominating pair graphs
• Canonical representations for circular-arc graphs using flip sets
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Interval graph limits
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• Tree-edges deletion problems with bounded diameter obstruction sets
• \(k\)-spine, 1-bend planarity
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• Two-layer planarization parameterized by feedback edge set
• scientific article; zbMATH DE number 1950547 (Why is no real title available?)
• scientific article; zbMATH DE number 1982187 (Why is no real title available?)
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• scientific article; zbMATH DE number 840682 (Why is no real title available?)
• scientific article; zbMATH DE number 861322 (Why is no real title available?)
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• On the complexity of the maximum biplanar subgraph problem
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• A graph-theoretic barcode ordering model for linked-reads
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Tree loop graphs
• On the parameterized complexity of layered graph drawing
• Some approximation algorithms for the clique partition problem in weighted interval graphs

This page was built for publication: Interval graphs and maps of DNA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1071684)