Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

DOI10.1016/S0166-218X(96)00063-7zbMath0873.92011MaRDI QIDQ5961617

R. Ravi, Vineet Bafna, Babu Narayanan

Publication date: 9 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-hard; molecular biology; maximum-weight independent set; performance ratio

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C90: Applications of graph theory

90C10: Integer programming

92C40: Biochemistry, molecular biology

92-08: Computational methods for problems pertaining to biology

Related Items

On the parameterized complexity of some optimization problems related to multiple-interval graphs, Using fractional primal-dual to schedule split intervals with demands, On the parameterized complexity of multiple-interval graph problems, Hardness of approximation for non-overlapping local alignments., Clique-detection models in computational biochemistry and genomics, An approximation algorithm for maximum triangle packing, A modified greedy algorithm for dispersively weighted 3-set cover, Improved Parameterized Algorithms for Weighted 3-Set Packing

Cites Work

• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• Simple heuristics for unit disk graphs
• Genome Rearrangements and Sorting by Reversals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item