Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem

References

• Avenali A. New algorithms for minimum span frequency assignment and maximum weighted stable set problems. (2001) . Ph.D. thesis, Department of Computer and Systems Science, University of Rome “La Sapienza,” Rome, ItalyGoogle Scholar
• Baker A. B. Intelligent backtracking on constraint satisfaction problems: Experimental and theoretical results. (1995) . Ph.D. thesis, University of Oregon, Eugene, ORGoogle Scholar
• Balas E., Yu C. S. Finding maximum clique in an arbitrary graph. SIAM J. Comput. (1986) 15:1054–1068Crossref, Google Scholar
• Chvátal V. Resolution search. Discrete Appl. Math. (1997) 73:81–99Crossref, Google Scholar
• Dixon H. E., Ginsberg M. L. Combining satisfiability techniques from AI and OR. Knowledge Engrg. Rev. (2000) 15:31–65Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of the NP-Completeness (1979) (Freeman, New York) Google Scholar
• Gaschnig J. Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems. Proc. Second Conf. Canadian Soc. Computational Stud. Intelligence (1978) Toronto, Ontario, Canada:268–277Google Scholar
• Gaschnig J. Performance measurement and analysis of certain search algorithms. (1979) . Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA. Available as Technical Report CMU-CS-79-124Google Scholar
• Ginsberg M. L. Dynamic backtracking. J. Artificial Intelligence Res. (1993) 1:25–46Crossref, Google Scholar
• Ginsberg M. L., McAllester D. A. GSAT and dynamic backtracking. Second Workshop on Principles and Practice of Constraint Programming (1994) Orcas Island, WA(Springer Verlag, London, UK) 243–265Crossref, Google Scholar
• Ginsberg M. L., Crawford J. M., Etherington D. W. Dynamic backtracking. (1996) . Technical report, Computational Intelligence Research Laboratory, University of Oregon, Eugene, ORGoogle Scholar
• Hooker J. N., Woodruff D. L. Constraint satisfaction methods for generating valid cuts. Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search (1998) (Kluwer, Boston, MA) 1–30Crossref, Google Scholar
• Hooker J. N.Logic-Based Methods for Optimization (2000) (Wiley, New York) Crossref, Google Scholar
• Hooker J. N., Ottosson G., Thorsteinsson E. S., Kim H.-J. A scheme for unifying optimization and constraint satisfaction methods. Knowledge Engrg. Rev. (2000) 15(1):11–30(special issue on AI/OR)Crossref, Google Scholar
• Lovász L., Plummer M. D.Matching Theory (1986) (North-Holland, Amsterdam, The Netherlands) Google Scholar
• Mannino C., Sassano A. An exact algorithm for the maximum stable set problem. Computational Optim. Appl. (1994) 3:243–258Crossref, Google Scholar
• Mannino C., Sassano A. Edge projection and the maximum cardinality stable set problem. DIMACS Ser. Discrete Math. and Theoret. Comput. Sci. (1996) 26:249–261Google Scholar
• McAllester D. A. Partial order backtracking. (1993) . Technical report, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Parker R. G., Rardin R. L.Discrete Optimization (1988) (Academic Press, London, UK) Google Scholar
• Robinson J. A. A machine-oriented logic based on the resolution principle. J. Assoc. Comput. Machinery (1965) 12:23–41Crossref, Google Scholar
• Rossi F., Smriglio S. A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. (2001) 28(2):63–74Crossref, Google Scholar
• Sanchis L. A., Jagota A. Some experimental and theoretical results on test case generators for the maximum clique problem. (1993) . Technical Report 93-69, DIMACS, Rutgers University, Piscataway, NJGoogle Scholar
• Stallman R. M., Sussman G. J. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence (1977) 9:135–196Crossref, Google Scholar
• Tsang E.Foundations of Constraint Satisfaction (1983) (Academic Press, London, UK) Google Scholar