Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

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

zbMATH Keywords

NP-hard problemfixed-parameter tractabilityexact algorithmsconsecutive ones propertycircular ones propertyforbidden submatrix characterization

Mathematics Subject Classification ID

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

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