The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree.

Abstract excerpt

The Gapped Consecutive-Ones Property (C1P) Problem, or the (k, δ)-C1P Problem is: given a binary matrix M and integers k and δ, decide if the columns of M can be ordered such that each row contains at most k blocks of 1's, and no two neighboring blocks of 1's are separated by a gap of more than δ 0's. This problem was introduced by Chauve et al. ( 2009b ). The classical polynomial-time solvable C1P Problem is...

Topics

Share this publication in a Topic to start or enrich a Post.

• Share to Algorithms
• Share to Computer Simulation