Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction

DOI10.1007/978-3-642-04744-2_5zbMath1333.68138arXiv0912.4196OpenAlexW1516846940MaRDI QIDQ3638844

Vivija P. You, Cedric Chauve, Tamon Stephen, Utz-Uwe Haus

Publication date: 28 October 2009

Published in: Comparative Genomics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.4196

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Genetics and epigenetics (92D10) Boolean and Hadamard matrices (15B34)

Related Items (3)

Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Hardness results on the gapped consecutive-ones property problem

Cites Work

• Unnamed Item
• Computational aspects of monotone dualization: a brief survey
• Random generation of combinatorial structures from a uniform distribution
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• A structure theorem for the consecutive 1's property
• A Simple Test for the Consecutive Ones Property
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees

This page was built for publication: Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction