Abstract
Given a set S, two collections C <sub>r</sub> and C <sub>b</sub> of non-empty subsets of S and a positive integer k < |S|, the minimum degree hypergraph (MDH) problem is to find a subset S′ of S such that S′ â̂© B ≠ â̂... for all B â̂̂ C <sub>b</sub> and |S′ â̂© R | ≤ k for all R â̂̂ C <sub>r</sub> . This paper presents a linear-time algorithm for the MDH problem with C <sub>r</sub> a C <sub>b</sub> having the consecutive ones property. The presented algorithm improves the previous upper bound from O(|S| <sup>2</sup> ). © 2013 Springer-Verlag Berlin Heidelberg.