A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row
From MaRDI portal
Publication:3007640
DOI10.1007/978-3-642-20712-9_29zbMath1332.68062MaRDI 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
Related Items
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
