On solving covering problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On solving covering problems

Full text

Pdf (332 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 33rd annual Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 197 - 202

Year of Publication: 1996

ISBN:0-89791-779-0

Author

Olivier Coudert

Synopsys Inc., 700 East Middlefield Rd., Mountain View, CA

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 30, Citation Count: 26

Additional Information:

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/240518.240555 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	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	2	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
	3	V. Chv~tal, "A Greedy Heuristic for the Set-Covering Problem", Math. Op. Res., 4-3, pp. 233-235, Aug. 1979.
	4	Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
	5	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]
	6	Srinivas Devadas , Abhijit Ghosh , Kurt Keutzer, Logic synthesis, McGraw-Hill, Inc., New York, NY, 1994
	7	J. F. Gimpel, "A Reduction Technique for Prime Implicant Tables", IEEE Trans. Elec. Comp., 14, pp. 535- 541, June 1965.
	8	D. S. Johnson, "Approximation Algorithms for Combinatorial Problems", d. Comp. Sys. Sci., 9, 1974.
	9	E. L. Jr. McCluskey, "Minimization of Boolean Functions", Bell Sys. Tech. dour., 35, pp. 1417-1444, April 1959.
	10	Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
	11	W. V. O. Quine, "On Cores and Prime Implicants of Truth Functions", Am. Math. Monthly, 66, pp. 755-760, 1959.
	12	S. Robinson, R. House, "Gimpel's Reduction Technique Extended to the Covering Problem With Costs", in IEEE Trans. Elec. Comp., 16, pp. 509-514, Aug. 1967.
	13	Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989

CITED BY 26

	Vasco M. Manquinho , João Marques-Silva, On using satisfiability-based pruning techniques in covering algorithms, Proceedings of the conference on Design, automation and test in Europe, p.356-363, March 27-30, 2000, Paris, France
	Olivier Coudert , Tsutomu Sasao, Two-level logic minimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Roberto Cordone , Fabrizio Ferrandi , Donatella Sciuto , Roberto Wolfler Calvo, An efficient heuristic approach to solve the unate covering problem, Proceedings of the conference on Design, automation and test in Europe, p.364-371, March 27-30, 2000, Paris, France
	Jesse Whittemore , Joonyoung Kim , Karem Sakallah, SATIRE: a new incremental satisfiability engine, Proceedings of the 38th conference on Design automation, p.542-545, June 2001, Las Vegas, Nevada, United States
	Luca P. Carloni , Patrick C. McGeer , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli, Trace driven logic synthesis—application to power minimization, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.581-588, November 09-13, 1997, San Jose, California, United States
	Barry Shackleford , Etsuko Okushi , Mitsuhiro Yasuda , Hisao Koizumi , Katsuhiko Seo , Takahashi Iwamoto , Hiroto Yasuura, High-performance hardware design and implementation of genetic algorithms, Hardware implementation of intelligent systems, Physica-Verlag GmbH, Heidelberg, Germany, 2001
	S. Liao , K. Keutzer , S. Tjiang , S. Devadas, A new viewpoint on code generation for directed acyclic graphs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.51-75, Jan. 1998
	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
	J. Van Praet , D. Lanneer , W. Geurts , G. Goossens, Processor modeling and code selection for retargetable compilation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.277-307, July 2001
	João P. Marques-Silva , Karem A. Sakallah, Boolean satisfiability in electronic design automation, Proceedings of the 37th conference on Design automation, p.675-680, June 05-09, 2000, Los Angeles, California, United States
	Pinhong Chen , Kurt Keutzer, Towards true crosstalk noise analysis, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.132-138, November 07-11, 1999, San Jose, California, United States
	Christian Plessl , Marco Platzner, Instance-Specific Accelerators for Minimum Covering, The Journal of Supercomputing, v.26 n.2, p.109-129, September 2003
	Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
	Peter Petrov , Alex Orailoglu, Low-power instruction bus encoding for embedded processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.8, p.812-826, August 2004
	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
	Inês Lynce , João P. Marques-Silva, An Overview of Backtrack Search Satisfiability Algorithms, Annals of Mathematics and Artificial Intelligence, v.37 n.3, p.307-326, March 2003
	Vasco M. Manquinho , João P. Marques-Silva, Satisfiability-Based Algorithms for Boolean Optimization, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.353-372, March 2004
	Zhaohui Fu , Sharad Malik, Solving the minimum-cost satisfiability problem using SAT based branch-and-bound search, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Luís Guerra e Silva , L. Miguel Silveira , Joöa Marques-Silva, Algorithms for solving Boolean satisfiability in combinational circuits, Proceedings of the conference on Design, automation and test in Europe, p.107-es, January 1999, Munich, Germany
	A. M. Brosa , J. Figueras, On Maximizing the Coverage of Catastrophic and Parametric Faults, Journal of Electronic Testing: Theory and Applications, v.16 n.3, p.251-258, June 2000
	O. Coudert, Solving Graph Optimization Problems with ZBDDs, Proceedings of the 1997 European conference on Design and Test, p.224, March 17-20, 1997
	Inês Lynce , João Marques-Silva, Efficient Data Structures for Backtrack Search SAT Solvers, Annals of Mathematics and Artificial Intelligence, v.43 n.1-4, p.137-152, January 2005
	Vasco M. Manquinho , Joao Marques-Silva, Effective Lower Bounding Techniques for Pseudo-Boolean Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.660-665, March 07-11, 2005
	Barry Shackleford , Greg Snider , Richard J. Carter , Etsuko Okushi , Mitsuhiro Yasuda , Katsuhiko Seo , Hiroto Yasuura, A High-Performance, Pipelined, FPGA-Based Genetic Algorithm Machine, Genetic Programming and Evolvable Machines, v.2 n.1, p.33-60, March 2001
	Michael E. Imhof , Christian G. Zoellin , Hans-Joachim Wunderlich , Nicolas Maeding , Jens Leenstra, Scan test planning for power reduction, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	John Homer , Xinming Ou, Sat-solving approaches to context-aware enterprise network security management, IEEE Journal on Selected Areas in Communications, v.27 n.3, p.315-322, April 2009