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

algorithminterval graphsrestriction mapsCircular restriction mapsrepresentation of DNA

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

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• 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

(22)

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

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)