Approximation algorithms for the consecutive ones submatrix problem on sparse matrices

DOI10.1007/978-3-540-30551-4_71MaRDI QIDQ5712170zbMATH OpenOpenAlexFDO

Authors Jinsong Tan, Louxin Zhang

Publication date 22 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b104582

Mathematics Subject Classification ID

Matrices of integers (15B36) Computational methods for sparse matrices (65F50) Approximation algorithms (68W25)

Recommendations

• The consecutive ones submatrix problem for sparse matrices
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• scientific article; zbMATH DE number 3848609
• On the consecutive ones property

Cited in

(13)

• Hardness results on the gapped consecutive-ones property problem
• A note on the consecutive ones submatrix problem.
• Obtaining matrices with the consecutive ones property by row deletions
• The consecutive ones submatrix problem for sparse matrices
• The maximum matrix contraction problem
• Upper and lower bounding procedures for the minimum caterpillar spanning problem
• Approximation of the Consecutive Ones Matrix Augmentation Problem
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A note on consecutive ones in a binary matrix
• Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems
• The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• A new characterization of matrices with the consecutive ones property
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

This page was built for publication: Approximation algorithms for the consecutive ones submatrix problem on sparse matrices

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