An efficient heuristic approach to solve the unate covering problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient heuristic approach to solve the unate covering problem

Full text

Publisher Site , Pdf

Pdf (143 KB)

Source

Design, Automation, and Test in Europe archive
Proceedings of the conference on Design, automation and test in Europe table of contents

Paris, France

Pages: 364 - 371

Year of Publication: 2000

ISBN:1-58113-244-1

Authors

Roberto Cordone	DEI - Politecnico di Milano
Fabrizio Ferrandi	DEI - Politecnico di Milano
Donatella Sciuto	DEI - Politecnico di Milano
Roberto Wolfler Calvo	ISIS - Joint Research Centre (JRC) - Ispra

Sponsors

EDAA : European Design Automation Association
SIGDA: ACM Special Interest Group on Design Automation
ECSI :
RAS : RAS
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society
IFIP : International Federation for Information Processing

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/343647.343799 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.

	1	E. Balas and A. Ho. Set Covering using cutting planes, heuristics and subgradient optimisation: A computational study. Mathematical P1vgramming Study, 12:37-60, 1980.
	2	J.E. Beasley. An algorithm for Set Covering problems. Emvpean Journal of Operational Research, 31:85-93, 1987.
	3	Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
	4	R.K. Brayton, P. C. McGeer, J. Sanghavi, and A. L. Sangiovanni-Vincentelli. A new exact minimizer for two-level logic synthesis. In T. Sasao, editor, Logic Synthesis and Optimization, pages 1-31. Kluwer Academic Publishers, Dordrecht, 1993.
	5	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	6	Alberto Caprara , Matteo Fischetti , Paolo Toth, A Heuristic Algorithm for the Set Covering Problem, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.72-84, June 03-05, 1996
	7	Sebastián Ceria , Paolo Nobili , Antonio Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming: Series A and B, v.81 n.2, p.215-228, April 1, 1998 [doi>10.1007/BF01581106]
	8	A.K. Chandra and G. Markowsky. On the number of prime implicants. Discrete Mathematics, 24:7-11, 1978.
	9	V. Chvfital. A greedy heuristic for the Set Covering problem. Mathematics of Operations Research, 4(3):233-235, August 1979.
	10	Olivier Coudert, Two-level logic minimization: an overview, Integration, the VLSI Journal, v.17 n.2, p.97-140, Oct. 1994 [doi>10.1016/0167-9260(94)00007-7]
	11	Olivier Coudert, On solving covering problems, Proceedings of the 33rd annual conference on Design automation, p.197-202, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240555]
	12	Olivier Coudert , Jean Christophe Madre , Henri Fraisse, A new viewpoint on two-level logic minimization, Proceedings of the 30th international conference on Design automation, p.625-630, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165071]
	13	M. L. Fisher , P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, v.36 n.6, p.674-688, Jun. 1990 [doi>10.1287/mnsc.36.6.674]
	14	Evguenii I. Goldberg , Luca P. Carloni , Tiziano Villa , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Negative thinking by incremental problem solving: application to unate covering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.91-98, November 09-13, 1997, San Jose, California, United States
	15	Stan Liao , Srinivas Devadas, Solving covering problems using LPR-based lower bounds, Proceedings of the 34th annual conference on Design automation, p.117-120, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266046]
	16	L. Lovfisz. On the ratio of optimal integral and tractional covers. Discrete Mathematics, 13:383-390, 1975.
	17	E.L. McCluskey Jr. Minimization of boolean functions. Bell System Technical Journal, 35:1417-1444, April 1959.
	18	Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
	19	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	20	W.V.O. Quine. On cores and prime implicants of truth functions. American Mathematics Monthly, 66:755-760, 1959.
	21	F. Somenzi. CUDD : Colorado University Decision Diagram Package. University of Colorado, Boulder, 1994.
	22	G.M. Swamy, P. McGeer, and R. K. Brayton. A tully Quine-McCluskey procedure using BDD's. Report UCB/ERL M92/127, UCB, November 1992. Also in: Proceedings of the International Workshop on Logic Synthesis, Lake Tahoe, CA, May 1993.
	23	T. Villa, T. Kam, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Explicit and implicit algorithms for binate covering problems. IEEE Transactions on Computers, 16(7):677-691, July 1997.

CITED BY 3

	Xiao Yu Li , Matthias F. Stallmann , Franc Brglez, Effective bounding techniques for solving unate and binate covering problems, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Roman Lysecky , Frank Vahid, On-chip logic minimization, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Nathan Clark , Amir Hormati , Scott Mahlke , Sami Yehia, Scalable subgraph mapping for acyclic computation accelerators, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea