Improved Exact Algorithms for MAX-SAT
作者： Jianer Chen , Iyad A. Kanj
关键词:
摘要: In this paper we present improved exact and parameterized algorithms for the maximum satisfiability problem. particular, give an algorithm that computes a truth assignment boolean formula F satisfying number of clauses in time O(1.3247m|F|), where m is F, |F| sum literals appearing each clause F. Moreover, given parameter k, O(1.3695kk2 + |F|) decides whether at least k exists. Both improve previous best by Bansal Raman
core.ac.uk
springer.com
sci-hub.st 参考文章(46)
Peter Rossmanith, Rolf Niedermeier, Jens Gramm, Edward A. Hirsch, New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT Electronic Colloquium on Computational Complexity. ,vol. 7, ,(2000)
David Eppstein, Richard Beigel, 3-Coloring in time O(1.3446n): a no-MIS algorithm ,(2000)
Jianer Chen, Iyad A. Kanj, On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms workshop on graph theoretic concepts in computer science. pp. 55- 65 ,(2001) , 10.1007/3-540-45477-2_7
Jianer Chen, Donald K. Friesen, Weijia Jia, Iyad A. Kanj, Using Nondeterminism to Design Efficient Deterministic Algorithms FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. pp. 120- 131 ,(2001) , 10.1007/3-540-45294-X_11
Rodney G. Downey, Michael R. Fellows, Ulrike Stege, Parameterized complexity: A framework for systematically confronting computational intractability. Contemporary Trends in Discrete Mathematics. pp. 49- 100 ,(1997)
W. A. Perkins, D. Pecora, T. A. Nguyen, T. J. Laffey, Checking an expert systems knowledge base for consistency and completeness international joint conference on artificial intelligence. pp. 375- 378 ,(1985)
Iyad Kanj, Weijia Jia, Jianer Chen, Donald K. Friesen, Using Nondeterminism to Design Deterministic Algorithms foundations of software technology and theoretical computer science. pp. 120- 131 ,(2001)
Pierre Hansen, Brigitte Jaumard, Algorithms for the maximum satisfiability problem Computing. ,vol. 44, pp. 279- 303 ,(1990) , 10.1007/BF02241270
Richard J. Wallace, Enhancing Maximum Satisfiablility Algorithms with Pure Literal Strategies AI '96 Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence. pp. 388- 401 ,(1996) , 10.1007/3-540-61291-2_67
Jianer Chen, Iyad A. Kanj, Weijia Jia, Vertex Cover: Further Observations and Further Improvements workshop on graph theoretic concepts in computer science. pp. 313- 324 ,(1999) , 10.1007/3-540-46784-X_30