On Physical Mapping and the consecutive ones property for sparse matrices

DOI10.1016/S0166-218X(96)00055-8zbMath0876.92011MaRDI QIDQ5961616

Jonathan E. Atkins, Martin Middendorf

Publication date: 25 November 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

NP-complete; fingerprints; molecular biology; clone library; physical mapping problem

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

68Q25: Analysis of algorithms and problem complexity

05C90: Applications of graph theory

68R10: Graph theory (including graph drawing) in computer science

92C40: Biochemistry, molecular biology

92D20: Protein sequences, DNA sequences

Related Items

A faster algorithm for finding minimum Tucker submatrices, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, The parameterized complexity of stabbing rectangles

Cites Work

• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the complexity of DNA physical mapping
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• Incidence matrices and interval graphs
• Polynomial Complete Consecutive Information Retrieval Problems
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Interval routing schemes
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques