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

biclique edge coveringbipartite graphBoolean matrixcomputational biologyfixed-parameter tractabilitygraph theorykernelisationNP-completeness

Mathematics Subject Classification ID

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

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

• 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
• 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 2234775 (Why is no real title available?)
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• On covering graphs by complete bipartite subgraphs
• Parameterized complexity
• Parametrized complexity theory.

Cited in

(7)

• On some FPT problems without polynomial Turing compressions
• Efficient approximation for restricted biclique cover problems
• Mod/Resc parsimony inference
• The parsimony principle for a class of model structures
• Problems and invariants connected with bicliques and multicliques of graphs
• K-balanced biclique partition: kernelization and efficient algorithms
• k-balanced biclique partition on signed bipartite graphs

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)