Mod/Resc parsimony inference: theory and application

DOI10.1016/J.IC.2011.03.008MaRDI QIDQ418168zbMATH OpenOpenAlexFDO

Authors Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstädter, Max Reuter, Olivier Duron, Marie-France Sagot

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.03.008

zbMATH Keywords

graph theorybipartite graphcomputational biologyNP-completenessfixed-parameter tractabilityBoolean matrixbiclique edge coveringkernelisation

Mathematics Subject Classification ID

Medical epidemiology (92C60) Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20)

Recommendations

• Mod/Resc parsimony inference
• Efficient approximation for restricted biclique cover problems
• The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability
• Covering graphs with few complete bipartite subgraphs
• Extended islands of tractability for parsimony haplotyping

Cites work

• scientific article; zbMATH DE number 3904663 (Why is no real title available?)
• scientific article; zbMATH DE number 4008576 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• Bicliques in graphs. I: Bounds on their number
• Covering graphs with few complete bipartite subgraphs
• Data reduction and exact algorithms for clique cover
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• On covering graphs by complete bipartite subgraphs
• Parametrized complexity theory.

Cited in

(5)

• The parsimony principle for a class of model structures
• Problems and invariants connected with bicliques and multicliques of graphs
• On some FPT problems without polynomial Turing compressions
• Efficient approximation for restricted biclique cover problems
• Mod/Resc parsimony inference

This page was built for publication: Mod/Resc parsimony inference: theory and application

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