Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings

Giovanni Battaglia, Roberto Grossi, Noemi Scutellà

A binary matrix satisfies the consecutive ones property (COP) if its columns can be permuted such that the ones in each row of the resulting matrix are consecutive. Equivalently, a…