Algorithimic Aspects of the Consecutive-Ones Property.
Michael Dom · Bulletin of the European Association for Theoretical Computer Science · 2009
We survey the consecutive-ones property of binary matrices. Herein, a binary matrix has the consecutive-ones property (C1P) if there is a permutation of its columns that places the 1s consecutively in every row. We provide an overview over connections to graph theory, characterizations, recognition algorithms, and applications such as integer linear programming and solving Set Cover.