Irredundant intervals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Irredundant intervals

Full text

Pdf (201 KB),

Ps (339 KB)

Source

Journal of Experimental Algorithmics (JEA) archive
Volume 1 , (1996) table of contents

Article No. 1

Year of Publication: 1996

ISSN:1084-6654

Author

Donald E. Knuth

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 62, Citation Count: 2

Additional Information:

appendices and supplements abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/235141.235146 What is a DOI?

APPENDICES and SUPPLEMENTS

p1-knuth_verbose.ch (1 KB),	The original cweb file (text and program) and a change file for more verbose output from the program; note that you need cweb installed to process the file; you can get cweb by anonymous ftp from labrea.stanford.edu in directory pub/cweb.

p1-knuth.w ,	The original cweb file (text and program) and a change file for more verbose output from the program; note that you need cweb installed to process the file; you can get cweb by anonymous ftp from labrea.stanford.edu in directory pub/cweb.

p1-knuth.c ,	The C program produced by running ctangle; note that you need the Stanford Graph Library installed to compile and link the C program; the Stanford Graph Library is available via anonymous ftp from labrea.stanford.edu in directory pub/sgb as file sgb.tar.gz.

ABSTRACT

This expository note presents simplifications of a theorem due to Gyri 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 The Stanford GraphBase.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Joseph C. Culberson , Robert A. Reckhow, Covering polygons is hard, Journal of Algorithms, v.17 n.1, p.2-44, July 1994 [doi>10.1006/jagm.1994.1025]
	2	András Frank , Tibor Jordán, Minimal edge-coverings of pairs of sets, Journal of Combinatorial Theory Series B, v.65 n.1, p.73-110, Sept. 1995 [doi>10.1006/jctb.1995.1044]
	3	D S Franzblau , D J Kleitman, An algorithm for covering polygons with rectangles, Information and Control, v.63 n.3, p.164-189, Dec. 1986 [doi>10.1016/S0019-9958(84)80012-1]
	4	{4} Ervin Györi, "A minimax theorem on intervals," <i>Journal of Combinatorial Theory</i> <b>B37</b> (1984), 1-9.
	5	{5} Donald E. Knuth and P. B. Bendix, "Simple word problems in universal algebras," in <i>Computational Problems in Abstract Algebra</i>, edited by J. Leech (Oxford: Pergamon, 1970), 263-297. Reprinted in <i>Automation of Reasoning</i>, edited by Jörg H. Siekmann and Graham Wrightson, <b>2</b> (Springer, 1983), 342-376.
	6	{6} Donald E. Knuth, <i>Fundamental Algorithms</i>, Volume 1 of <i>The Art of Computer Programming</i> (Reading, Massachusetts: Addison-Wesley, 1968), xxii+634 pp.
	7	{7} Donald E. Knuth, <i>Sorting and Searching</i>, Volume 3 of <i>The Art of Computer Programming</i> (Reading, Massachusetts: Addison-Wesley, 1973), xii+722 pp. + foldout illustration.
	8	Donald E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, ACM Press, New York, NY, 1993
	9	Donald Ervin Knuth , Silvio Levy, The CWEB System of Structured Documentation: Version 3.0, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
	10	{10} Anna Lubiw, "A weighted min-max relation for intervals," <i>Journal of Combinatorial Theory</i> <b>B53</b> (1991), 173-194.

CITED BY 2

	András A. Benczúr, Pushdown-reduce: an algorithm for connectivity augmentation and poset covering problems, Discrete Applied Mathematics, v.129 n.2-3, p.233-262, 01 August 2003
	László A. Végh , András A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia