A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row

DOI10.1007/978-3-642-20712-9_29zbMath1332.68062OpenAlexW2101954823MaRDI QIDQ3007640

Stéphane Vialette, Guillaume Blin, Romeo Rizzi

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean and Hadamard matrices (15B34)

Related Items (2)

A faster algorithm for finding minimum Tucker submatrices ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• A new characterization of matrices with the consecutive ones property
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Approximation algorithms for hitting objects with straight lines
• Structural properties and decomposition of linear balanced matrices
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• PC trees and circular-ones arrangements.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Set covering with almost consecutive ones property
• Incidence matrices and interval graphs
• A structure theorem for the consecutive 1's property
• A Simple Test for the Consecutive Ones Property
• A Faster Algorithm for Finding Minimum Tucker Submatrices
• Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Optimal Capacity Scheduling—I
• Cyclic Scheduling via Integer Programs with Circular Ones
• Disjoint paths in a network
• Polynomial Complete Consecutive Information Retrieval Problems
• Algorithms – ESA 2004

This page was built for publication: A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row