Parameterizing MAX SNP Problems Above Guaranteed Values

DOI10.1007/11847250_4MaRDI QIDQ3499722zbMATH OpenOpenAlexFDO

Authors Meena Mahajan, Venkatesh Raman, Somnath Sikdar

Publication date 3 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11847250_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1877046
• scientific article; zbMATH DE number 1945152
• Maximum bounded \(H\)-matching is Max SNP-complete
• scientific article; zbMATH DE number 2040938
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The complexity of the single individual SNP haplotyping problem
• Efficient Algorithms for SNP Haplotype Block Selection Problems
• Maximizing a Family of Optimal Statistics over a Nuisance Parameter with Applications to Genetic Data Analysis
• Improved MAX SNP-hard results for finding an edit distance between unordered trees
• Some MAX SNP-hard results concerning unordered labeled trees

Cited in

(9)

• Parameterizing above or below guaranteed values
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• A probabilistic approach to problems parameterized above or below tight bounds
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• A probabilistic approach to problems parameterized above or below tight bounds
• On the parameterized vertex cover problem for graphs with perfect matching
• Maximum bounded 3-dimensional matching is MAX SNP-complete

This page was built for publication: Parameterizing MAX SNP Problems Above Guaranteed Values

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499722)