Irredundant intervals
| dc.creator | Knuth, Donald E. | |
| dc.date | 1996-06-07 | |
| dc.date.accessioned | 2026-07-07T09:15:34Z | |
| dc.date.available | 2026-07-07T09:15:34Z | |
| dc.description | 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}. | |
| dc.identifier | https://arxiv.org/abs/math/9606232 | |
| dc.identifier | http://arxiv.org/abs/math/9606232 | |
| dc.identifier | ACM J. Exp. Algorithmics 1 (1996), 19pp | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/153061 | |
| dc.subject | Combinatorics | |
| dc.title | Irredundant intervals | |
| dc.type | text |