Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees
verfasst von : Giovanni Battaglia, Roberto Grossi, Noemi Scutellà
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A binary matrix satisfies the
consecutive ones property
(C1P) if its columns can be permuted such that the 1s in each row of the resulting matrix are consecutive. Equivalently, a family of
sets
F
= {
Q
1
,...,
Q
m
}, where
Q
i
⊆
R
for some universe
R
, satisfies the C1P if the symbols in
R
can be permuted such that the elements of each set
Q
i
∈
F
occur consecutively, as a contiguous segment of the permutation of
R
’s symbols. Motivated by combinatorial problems on sequences with repeated symbols, we consider the C1P version on
multisets
and prove that counting the orderings (permutations) thus generated is #P-complete. We prove completeness results also for counting the permutations generated by PQ-trees (which are related to the C1P), thus showing that a polynomial-time algorithm is unlikely to exist when dealing with multisets and sequences with repeated symbols.