Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

DOI10.1016/J.JCSS.2009.07.001MaRDI QIDQ972381zbMATH OpenOpenAlexFDO

Authors Michael Dom, Jiong Guo, Rolf Niedermeier

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

zbMATH Keywords

circular ones propertyconsecutive ones propertyexact algorithmsfixed-parameter tractabilityforbidden submatrix characterizationNP-hard problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• Algorithms and Computation
• FPT algorithms for consecutive ones submatrix problems
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• The consecutive ones submatrix problem for sparse matrices

Cites work

• A certifying algorithm for the consecutive-ones property
• A fixed-parameter approach to 2-layer planarization
• A note on the consecutive ones submatrix problem.
• A Simple Test for the Consecutive Ones Property
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A structure theorem for the consecutive 1's property
• Algorithms – ESA 2004
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• Approximation algorithms for hitting objects with straight lines
• 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
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Cyclic Scheduling via Integer Programs with Circular Ones
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Graph Drawing
• scientific article; zbMATH DE number 5606342 (Why is no real title available?)
• scientific article; zbMATH DE number 1187154 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Incidence matrices and interval graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Matrix characterizations of circular-arc graphs
• On Physical Mapping and the consecutive ones property for sparse matrices
• On the consecutive ones property
• Optimal Capacity Scheduling—I
• Parameterized algorithmics for linear arrangement problems
• Parametrized complexity theory.
• PC trees and circular-ones arrangements.
• Polynomial Complete Consecutive Information Retrieval Problems
• Recognizing graphs without asteroidal triples
• Set covering with almost consecutive ones property
• SOFSEM 2005: Theory and Practice of Computer Science
• Station location -- complexity and approximation
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The consecutive ones submatrix problem for sparse matrices
• The simultaneous consecutive ones problem
• The weighted consecutive ones problem for a fixed number of rows or columns.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(24)

• The weighted consecutive ones problem for a fixed number of rows or columns.
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• 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
• The consecutive ones submatrix problem for sparse matrices
• FPT algorithms for consecutive ones submatrix problems
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• Measuring indifference: unit interval vertex deletion
• THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• A faster algorithm for finding minimum Tucker submatrices
• Approximation of the Consecutive Ones Matrix Augmentation Problem
• Two-layer planarization parameterized by feedback edge set
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A bad submatrix is easy to find
• A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix
• scientific article; zbMATH DE number 2104735 (Why is no real title available?)
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• Algorithms and Computation
• Temporal interval cliques and independent sets
• On computing optimal linear diagrams
• A faster algorithm for finding minimum Tucker submatrices
• Classical complexity and fixed-parameter tractability of simultaneous consecutive ones submatrix \& editing problems

This page was built for publication: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972381)