Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
From MaRDI portal
Publication:972381
DOI10.1016/j.jcss.2009.07.001zbMath1201.68153OpenAlexW2112307988MaRDI QIDQ972381
Michael Dom, Rolf Niedermeier, Jiong Guo
Publication date: 25 May 2010
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.07.001
NP-hard problemfixed-parameter tractabilityexact algorithmsconsecutive ones propertycircular ones propertyforbidden submatrix characterization
Related Items (12)
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Temporal interval cliques and independent sets ⋮ On computing optimal linear diagrams ⋮ A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Minimising the number of gap-zeros in binary matrices ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
- Recognizing graphs without asteroidal triples
- Parameterized algorithmics for linear arrangement problems
- The simultaneous consecutive ones problem
- Approximation algorithms for hitting objects with straight lines
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the consecutive ones property
- The weighted consecutive ones problem for a fixed number of rows or columns.
- PC trees and circular-ones arrangements.
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- A note on the consecutive ones submatrix problem.
- Set covering with almost consecutive ones property
- Incidence matrices and interval graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- A fixed-parameter approach to 2-layer planarization
- A structure theorem for the consecutive 1's property
- Matrix characterizations of circular-arc graphs
- The consecutive ones submatrix problem for sparse matrices
- Station Location - Complexity and Approximation.
- A Simple Test for the Consecutive Ones Property
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation of the Consecutive Ones Matrix Augmentation Problem
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Optimal Capacity Scheduling—I
- Cyclic Scheduling via Integer Programs with Circular Ones
- Polynomial Complete Consecutive Information Retrieval Problems
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
- Algorithms – ESA 2004
- SOFSEM 2005: Theory and Practice of Computer Science
- Graph Drawing
- On Physical Mapping and the consecutive ones property for sparse matrices
This page was built for publication: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
