Mathematics – Combinatorics
Scientific paper
1996-06-07
ACM J. Exp. Algorithmics 1 (1996), 19pp
Mathematics
Combinatorics
Scientific paper
This expository note presents simplifications of a theorem due to Gy\H{o}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}.
No associations
LandOfFree
Irredundant intervals does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Irredundant intervals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Irredundant intervals will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-724294