Lialina, A. A. On the complexity of unique circuit SAT. (English. Russian original) Zbl 1442.68053 J. Math. Sci., New York 247, No. 3, 457-466 (2020); translation from Zap. Nauchn. Semin. POMI 475, 122-136 (2018). MSC: 68Q06 68R07 68W40 94C11 PDF BibTeX XML Cite \textit{A. A. Lialina}, J. Math. Sci., New York 247, No. 3, 457--466 (2020; Zbl 1442.68053); translation from Zap. Nauchn. Semin. POMI 475, 122--136 (2018) Full Text: DOI
Bykova, V. V. On the asymptotic solution of a special type recurrence relations and the Kullmann-Luckhardt’s technology. (Russian. English summary) Zbl 07310227 Prikl. Diskretn. Mat. 2013, No. 4(22), 56-66 (2013). MSC: 68 65 PDF BibTeX XML Cite \textit{V. V. Bykova}, Prikl. Diskretn. Mat. 2013, No. 4(22), 56--66 (2013; Zbl 07310227) Full Text: MNR
Xu, Xuelin; Gao, Zongsheng; Xu, Ke A tighter upper bound for random MAX \(2\)-SAT. (English) Zbl 1260.68164 Inf. Process. Lett. 111, No. 3, 115-119 (2011). MSC: 68Q17 68Q25 PDF BibTeX XML Cite \textit{X. Xu} et al., Inf. Process. Lett. 111, No. 3, 115--119 (2011; Zbl 1260.68164) Full Text: DOI
Chen, Jianer; Liu, Yang An improved SAT algorithm in terms of formula length. (English) Zbl 1253.68166 Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 144-155 (2009). MSC: 68Q25 68T20 PDF BibTeX XML Cite \textit{J. Chen} and \textit{Y. Liu}, Lect. Notes Comput. Sci. 5664, 144--155 (2009; Zbl 1253.68166) Full Text: DOI
Fagnot, Isabelle; Lelandais, Gaëlle; Vialette, Stéphane Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs. (English) Zbl 1146.05313 J. Discrete Algorithms 6, No. 2, 178-191 (2008). MSC: 05C85 05C90 05C70 92D15 92D20 PDF BibTeX XML Cite \textit{I. Fagnot} et al., J. Discrete Algorithms 6, No. 2, 178--191 (2008; Zbl 1146.05313) Full Text: DOI
Riege, Tobias; Rothe, Jörg; Spakowski, Holger; Yamamoto, Masaki An improved exact algorithm for the domatic number problem. (English) Zbl 1185.68843 Inf. Process. Lett. 101, No. 3, 101-106 (2007). MSC: 68W20 PDF BibTeX XML Cite \textit{T. Riege} et al., Inf. Process. Lett. 101, No. 3, 101--106 (2007; Zbl 1185.68843) Full Text: DOI
Madsen, Bolette Ammitzbøll An algorithm for exact satisfiability analysed with the number of clauses as parameter. (English) Zbl 1185.68647 Inf. Process. Lett. 97, No. 1, 28-30 (2006). MSC: 68T20 68W05 PDF BibTeX XML Cite \textit{B. A. Madsen}, Inf. Process. Lett. 97, No. 1, 28--30 (2006; Zbl 1185.68647) Full Text: DOI
Shen, Haiou; Zhang, Hantao Improving exact algorithms for MAX-2-SAT. (English) Zbl 1086.68058 Ann. Math. Artif. Intell. 44, No. 4, 419-436 (2005). MSC: 68Q25 68T20 68R10 PDF BibTeX XML Cite \textit{H. Shen} and \textit{H. Zhang}, Ann. Math. Artif. Intell. 44, No. 4, 419--436 (2005; Zbl 1086.68058) Full Text: DOI
Zhang, Hantao; Shen, Haiou; Manyà, Felip Exact algorithms for MAX-SAT. (English) Zbl 1261.68073 Dahn, Ingo (ed.) et al., FTP’2003: 4th international workshop on first-order theorem proving. Proceedings of the workshop (in connection with RDP’03, federated conference on rewriting, deduction and programming), Valencia, Spain, June 12–14, 2003. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 86, No. 1, 190-203 (2003). MSC: 68Q25 68Q17 PDF BibTeX XML Cite \textit{H. Zhang} et al., Electron. Notes Theor. Comput. Sci. 86, No. 1, 190--203 (2003; Zbl 1261.68073) Full Text: DOI
Shen, Haiou; Zhag, Hantao An empirical study of Max-2-sat phase transitions. (English) Zbl 1179.68148 Kranakis, Evangelos (ed.) et al., Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14–16, 2003. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 16, 80-92 (2003). MSC: 68T20 PDF BibTeX XML Cite \textit{H. Shen} and \textit{H. Zhag}, Electron. Notes Discrete Math. 16, 80--92 (2003; Zbl 1179.68148) Full Text: DOI
Niedermeier, Rolf; Rossmanith, Peter An efficient fixed-parameter algorithm for 3-hitting set. (English) Zbl 1118.68511 J. Discrete Algorithms 1, No. 1, 89-102 (2003). MSC: 68Q25 PDF BibTeX XML Cite \textit{R. Niedermeier} and \textit{P. Rossmanith}, J. Discrete Algorithms 1, No. 1, 89--102 (2003; Zbl 1118.68511) Full Text: DOI
Kullmann, Oliver Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets. (English) Zbl 1029.68079 Discrete Appl. Math. 130, No. 2, 209-249 (2003). MSC: 68Q25 PDF BibTeX XML Cite \textit{O. Kullmann}, Discrete Appl. Math. 130, No. 2, 209--249 (2003; Zbl 1029.68079) Full Text: DOI
Hirsch, Edward A. Worst-case study of local search for MAX-\(k\)-SAT. (English) Zbl 1051.68079 Discrete Appl. Math. 130, No. 2, 173-184 (2003). MSC: 68Q25 PDF BibTeX XML Cite \textit{E. A. Hirsch}, Discrete Appl. Math. 130, No. 2, 173--184 (2003; Zbl 1051.68079) Full Text: DOI
Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. (English) Zbl 1051.68078 Discrete Appl. Math. 130, No. 2, 139-155 (2003). MSC: 68Q25 PDF BibTeX XML Cite \textit{J. Gramm} et al., Discrete Appl. Math. 130, No. 2, 139--155 (2003; Zbl 1051.68078) Full Text: DOI
Nikolenko, S. I. Hard satisfiable instances for DPLL-type algorithms. (English. Russian original) Zbl 1101.68600 J. Math. Sci., New York 126, No. 3, 1205-1209 (2005); translation from Zap. Nauch. Semin. POMI 293, 139-148 (2002). MSC: 68Q17 PDF BibTeX XML Cite \textit{S. I. Nikolenko}, J. Math. Sci., New York 126, No. 3, 1205--1209 (2002; Zbl 1101.68600); translation from Zap. Nauch. Semin. POMI 293, 139--148 (2002) Full Text: DOI
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search. (English) Zbl 1061.68071 Theor. Comput. Sci. 289, No. 1, 69-83 (2002). MSC: 68Q25 PDF BibTeX XML Cite \textit{E. Dantsin} et al., Theor. Comput. Sci. 289, No. 1, 69--83 (2002; Zbl 1061.68071) Full Text: DOI
Dantsin, Evgeny; Gavrilovich, Michael; Hirsch, Edward A.; Konev, Boris MAX SAT approximation beyond the limits of polynomial-time approximation. (English) Zbl 0990.03006 Ann. Pure Appl. Logic 113, No. 1-3, 81-94 (2002). MSC: 03B35 68W25 68Q25 03B05 03B25 PDF BibTeX XML Cite \textit{E. Dantsin} et al., Ann. Pure Appl. Logic 113, No. 1--3, 81--94 (2002; Zbl 0990.03006) Full Text: DOI