Irredundant intervals

Abstract

This expository note presents simplifications of a theorem due to Győri and an algorithm due to Franzblau and Kleitman: Given a family $F$ of $m$ intervals on a linearly ordered set of $n$ elements, we can construct in $O(m+n{)}^2$ steps an irredundant subfamily having maximum cardinality, as well as a generating family having minimum cardinality. The algorithm is of special interest because it solves a problem analogous to finding a maximum independent set, but on a class of objects that is more general than a matroid. This note is also a complete, runnable computer program, which can be used for experiments in conjunction with the public-domain software of {\sl The Stanford GraphBase}.