Interval graphs and maps of DNA

DOI10.1007/BF02460022zbMath0585.92015OpenAlexW4237922239WikidataQ54703998 ScholiaQ54703998MaRDI QIDQ1071684

Jerrold R. Griggs, Michael S. Waterman

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)

Related Items (18)

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

Cites Work

• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Representation of a finite graph by a set of intervals on the real line
• Incidence matrices with the consecutive 1’s property
• A Characterization of Comparability Graphs and of Interval Graphs

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