Generating all maximal independent sets of bounded-degree hypergraphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generating all maximal independent sets of bounded-degree hypergraphs

Full text

Pdf (1.40 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the tenth annual conference on Computational learning theory table of contents

Nashville, Tennessee, United States

Pages: 211 - 217

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Nina Mishra	Computer Science Department, University of Illinois at Urbana-Champaign, Urbana, IL
Leonard Pitt	Computer Science Department, University of Illinois at Urbana-Champaign, Urbana, IL

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 24, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/267460.267500 What is a DOI?

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.

	ABK+97	Howard Aizenstein , Avrim Blum , Roni Khardon , Eyal Kushilevitz , Leonard Pitt , Dan Roth, On Learning Read-k-Satisfy-j DNF, SIAM Journal on Computing, v.27 n.6, p.1515-1530, Dec. 1998 [doi>10.1137/S0097539794274398]
	AHHPar	Howard Aizenstein , Tibor Hegedűs , Lisa Hellerstein , Leonard Pitt, Complexity theoretic hardness results for query learning, Computational Complexity, v.7 n.1, p.19-53, Jul. 1998 [doi>10.1007/PL00001593]
	AHK93	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	BCG+96	Nader H. Bshouty , Richard Cleve , Ricard Gavaldà , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning, Journal of Computer and System Sciences, v.52 n.3, p.421-433, June 1996 [doi>10.1006/jcss.1996.0032 ]
	BHH95a	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Arithmetic Read-Once Formulas, SIAM Journal on Computing, v.24 n.4, p.706-735, Aug. 1995 [doi>10.1137/S009753979223664X]
	BHH95b	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas over generalized bases, Journal of Computer and System Sciences, v.50 n.3, p.521-542, June 1995 [doi>10.1006/jcss.1995.1042 ]
	BI95	Jan C. Bioch , Toshihide Ibaraki, Complexity of identification and dualization of positive Boolean functions, Information and Computation, v.123 n.1, p.50-63, Nov. 15, 1995 [doi>10.1006/inco.1995.1157 ]
	Bsh95	Nader H. Bshouty, Exact learning Boolean functions via the monotone theory, Information and Computation, v.123 n.1, p.146-153, Nov. 15, 1995 [doi>10.1006/inco.1995.1164 ]
	EG95	Thomas Eiter , Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, v.24 n.6, p.1278-1304, Dec. 1995 [doi>10.1137/S0097539793250299]
	FK96	Michael L. Fredman , Leonid Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, v.21 n.3, p.618-628, Nov. 1996 [doi>10.1006/jagm.1996.0062 ]
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	GK95	Vladimir Gurvich and Leonid Khachiyan. Generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions. Technical Report, LCSR- TR-251, Dept of Computer Science, Rutgers University, Discrete Applied Math, to appear, August 1995.
	HMP97	Haym Hirsh, Nina Mishra, and Leonard Pitt. Version spaces without boundary sets. AAAI, 1997. To appear.
	JPY88	David S. Johnson , Christos H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, v.27 n.3, p.119-123, March 25, 1988 [doi>10.1016/0020-0190(88)90065-8 ]
	Kha95	Roni Khardon. Translating between horn representations and their characteristic models. Journal of AI Research, 3:349-372, 1995.
	KKS93	H. A. Kautz, M. J. Kearns, and B. Selman. Reasoning with characteristic models. In Proceedings of the 11th National Conference on Artificial Intelligence, pages 34-39, Washington, DC, July 1993. AAAI Press.
	KM95	Jyrki Kivinen , Heikki Mannila, Approximate inference of functional dependencies from relations, Theoretical Computer Science, v.149 n.1, p.129-149, Sept. 18, 1995
	KMR95	Roni Khardon, Heikki Mannila, and Dan Roth. Reasoning with examples: Propositional formulae and database dependencies. Technical Report, TR-15-95, Harvard University, 1995.
	KR94	Roni Khardon , Dan Roth, Reasoning with models, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1148-1153, October 1994, Seattle, Washington, United States
	KW85	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
	LLK80	E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM Journal on Computing, 9(3):558-565, August 1980.
	Mit82	Tom Mitchell. Generalization as search. Art. Int., 18:203-226, 1982.
	MR92a	Heikki Mannila , Kari-Jouko Räihä, On the complexity of inferring functional dependencies, Discrete Applied Mathematics, v.40 n.2, p.237-243, Dec. 10, 1992 [doi>10.1016/0166-218X(92)90031-5 ]
	MR92b	Heikki Mannila , Kari-Jouko Räihä, The design of relational databases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
	MT96	Heikki Mannila and Hannu Toivonen. On an algorithm for finding all interesting sentences. Cybernetics and Systems, R. Trappl, ed., pages 973-978, 1996.
	PR94a	Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181063]
	PR94b	Krishnan Pillaipakkamnatt , Vijay Raghavan, Read-twice DNF formulas are properly learnable, Proceedings of the first European conference on Computational learning theory, p.121-132, October 1994, Royal Holloway, Univ. of London, United Kingdom
	PV88	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	SK91	Bart Selman and Henry Kautz. Knowledge compilation using horn approximations. In Kathleen Dean, Thomas L.; McKeown, editor, Proceedings of the 9th National Conference on Artificial Intelligence, pages 904- 909. MIT Press, July 1991.
	TIAS77	Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3):505-517, September 1977.

CITED BY 5

	Magnus Wahlström, Exact algorithms for finding minimum transversals in rank-3 hypergraphs, Journal of Algorithms, v.51 n.2, p.107-121, May 2004
	David Eppstein, All maximal independent sets and dynamic dominance for sparse graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Robert H. Sloan , Ken Takata , György Turán, On frequent sets of Boolean matrices, Annals of Mathematics and Artificial Intelligence, v.24 n.1-4, p.193-209, 1998
	Thomas Eiter , Georg Gottlob , Kazuhisa Makino, New results on monotone dualization and generating hypergraph transversals, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003