Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings

DOI10.1016/j.ic.2012.08.005zbMath1252.68133OpenAlexW1986583537MaRDI QIDQ690497

Roberto Grossi, Giovanni Battaglia, Noemi Scutellà

Publication date: 27 November 2012

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

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

zbMATH Keywords

complexityPQ-treesmultisetsconsecutive ones propertycounting permutationssequences with repeated symbols

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• Consecutive block minimization is 1.5-approximable
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• Efficient text fingerprinting via Parikh mapping
• A new planarity test
• Fast algorithms to enumerate all common intervals of two permutations
• Incidence matrices and interval graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Counting the Number of Hamilton Cycles in Random Digraphs
• Polynomial Complete Consecutive Information Retrieval Problems
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Hamilton Cycles in Random Regular Digraphs
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Counting the Orderings for Multisets in Consecutive Ones Property and PQ-Trees
• Computational Complexity
• File organization

This page was built for publication: Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings