Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
From MaRDI portal
Publication:5961617
DOI10.1016/S0166-218X(96)00063-7zbMath0873.92011MaRDI QIDQ5961617
Babu Narayanan, R. Ravi, Vineet Bafna
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
Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Integer programming (90C10) Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08)
Related Items
A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs, An approximation algorithm for maximum packing of 3-edge paths, Recognizing \(d\)-interval graphs and \(d\)-track interval graphs, On spectrum sharing games, Using fractional primal-dual to schedule split intervals with demands, Optimizing experimental design in genetics, Local improvement algorithms for a path packing problem: a performance analysis based on linear programming, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Interval scheduling and colorful independent sets, Improved Parameterized Algorithms for Weighted 3-Set Packing, Scheduling split intervals with non-uniform demands, Hardness of approximation for non-overlapping local alignments., Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs, 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, On the parameterized complexity of multiple-interval graph problems, A local search algorithm for binary maximum 2-path partitioning
Cites Work
