On the complexity of DNA physical mapping
From MaRDI portal
Publication:1338883
DOI10.1006/aama.1994.1009zbMath0806.92007OpenAlexW2095075515WikidataQ60307348 ScholiaQ60307348MaRDI QIDQ1338883
Ron Shamir, Martin Charles Golumbic, Haim Kaplan
Publication date: 23 November 1994
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2dab86636acbf83457f8d5bc2de15611bf42dd9c
Graph theory (including graph drawing) in computer science (68R10) Biochemistry, molecular biology (92C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The graph sandwich problem for 1-join composition is NP-complete ⋮ An integer programming model for the Minimum Interval Graph Completion Problem ⋮ Planar Disjoint-Paths Completion ⋮ Additive approximation of generalized Turán questions ⋮ A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ Can transitive orientation make sandwich problems easier? ⋮ Planar disjoint-paths completion ⋮ Additive approximation for edge-deletion problems ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Good characterizations and linear time recognition for 2-probe block graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Polynomial kernels for proper interval completion and related problems ⋮ The interval order polytope of a digraph ⋮ Edge deletion to tree-like graph classes ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Interval graph limits ⋮ Recognition of probe proper interval graphs ⋮ On the complexity of computing treebreadth ⋮ Intervalizing k-colored graphs ⋮ Complexity issues for the sandwich homogeneous set problem ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ Near-optimal solutions for the generalized max-controlled set problem ⋮ Complexity classification of some edge modification problems ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ NP-completeness results for edge modification problems ⋮ On Physical Mapping and the consecutive ones property for sparse matrices ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Characterizing and recognizing probe block graphs ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Unnamed Item ⋮ Hardness of edge-modification problems ⋮ On the proper intervalization of colored caterpillar trees ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Matrix sandwich problems ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Tractability and hardness of flood-filling games on trees ⋮ The Proper Interval Colored Graph problem for caterpillar trees ⋮ Exact algorithms for intervalizing coloured graphs
This page was built for publication: On the complexity of DNA physical mapping
