Approximation of the Consecutive Ones Matrix Augmentation Problem

DOI10.1137/0214052MaRDI QIDQ3694717zbMATH OpenOpenAlexFDO

Authors Marinus Veldhorst

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214052

zbMATH Keywords

analysis of algorithmsapproximation algorithmsconsecutive ones propertyNP-completenesssparse matrix storage scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

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

Cited in

(3)

• Minimising the number of gap-zeros in binary matrices
• The maximum matrix contraction problem
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

This page was built for publication: Approximation of the Consecutive Ones Matrix Augmentation Problem

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