Irredundant intervals

DOI10.1145/235141.235146MaRDI QIDQ5463365zbMATH OpenOpenAlexFDO

Authors Donald E. Knuth

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9606232, http://www.jea.acm.org/1996/KnuthIntervals/

zbMATH Keywords

Franzblau and Kleitmangenerating familyGyöri

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Abstract: This expository note presents simplifications of a theorem due to GyH{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}.

Recommendations

• Irredundant Set Faster Than O(2 n )
• scientific article; zbMATH DE number 4197287
• scientific article; zbMATH DE number 3892606
• A fast algorithm for finding interlocking sets
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

Cited in

(7)

• A fast algorithm for finding interlocking sets
• Finding minimum generators of path systems
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• Jump number of two-directional orthogonal ray graphs
• scientific article; zbMATH DE number 3851100 (Why is no real title available?)
• Maximum independent set for intervals by divide and conquer with pruning
• scientific article; zbMATH DE number 1136097 (Why is no real title available?)

Describes a project that uses

Uses Software

• GraphBase

This page was built for publication: Irredundant intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463365)