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

DOI10.1016/j.ic.2012.08.005zbMath1252.68133MaRDI 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

complexity; PQ-trees; multisets; consecutive ones property; counting permutations; sequences with repeated symbols

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W32: Algorithms on strings

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