Bourreau, E.; Fleury, G.; Lacomme, P. Adiabatic based algorithm for SAT: a comprehensive algorithmic description. (English) Zbl 07757290 Physica A 629, Article ID 129206, 20 p. (2023). MSC: 82-XX PDFBibTeX XMLCite \textit{E. Bourreau} et al., Physica A 629, Article ID 129206, 20 p. (2023; Zbl 07757290) Full Text: DOI arXiv
Rad, N. Jafari; Maimani, H. R.; Momeni, M.; Mahid, F. Rahimi On the double Roman bondage numbers of graphs. (English) Zbl 1516.05177 Discrete Math. Algorithms Appl. 14, No. 8, Article ID 2250046, 14 p. (2022). MSC: 05C69 PDFBibTeX XMLCite \textit{N. J. Rad} et al., Discrete Math. Algorithms Appl. 14, No. 8, Article ID 2250046, 14 p. (2022; Zbl 1516.05177) Full Text: DOI arXiv
Poureidi, Abolfazl; Rad, Nader Jafari Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \(\{2\}\)-domination number. (English) Zbl 1492.05120 Discuss. Math., Graph Theory 42, No. 3, 709-726 (2022). MSC: 05C69 05C85 PDFBibTeX XMLCite \textit{A. Poureidi} and \textit{N. J. Rad}, Discuss. Math., Graph Theory 42, No. 3, 709--726 (2022; Zbl 1492.05120) Full Text: DOI
Hasan, Md. Manzurul; Mondal, Debajyoti; Rahman, Md. Saidur Positive planar satisfiability problems under 3-connectivity constraints. (English) Zbl 07533879 Theor. Comput. Sci. 917, 81-93 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{Md. M. Hasan} et al., Theor. Comput. Sci. 917, 81--93 (2022; Zbl 07533879) Full Text: DOI arXiv
Xu, Chao; Li, Wenjun; Wang, Jianxin; Yang, Yongjie An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses. (English) Zbl 1481.90280 J. Comb. Optim. 42, No. 3, 524-542 (2021). MSC: 90C27 90C57 PDFBibTeX XMLCite \textit{C. Xu} et al., J. Comb. Optim. 42, No. 3, 524--542 (2021; Zbl 1481.90280) Full Text: DOI
Poureidi, A. Algorithmic aspects of Roman graphs. (English) Zbl 1468.05285 J. Algebr. Syst. 9, No. 1, 119-135 (2021). MSC: 05C85 05C69 PDFBibTeX XMLCite \textit{A. Poureidi}, J. Algebr. Syst. 9, No. 1, 119--135 (2021; Zbl 1468.05285) Full Text: DOI
Lincoln, Andrea; Vyas, Nikhil Algorithms and lower bounds for cycles and walks: small space and sparse graphs. (English) Zbl 07650359 Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 11, 17 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Lincoln} and \textit{N. Vyas}, LIPIcs -- Leibniz Int. Proc. Inform. 151, Article 11, 17 p. (2020; Zbl 07650359) Full Text: DOI
Alexandersson, Per; Restadh, Petter LaserTank is NP-complete. (English) Zbl 07441080 Slamanig, Daniel (ed.) et al., Mathematical aspects of computer and information sciences. 8th international conference, MACIS 2019, Gebze, Turkey, November 13–15, 2019. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11989, 333-338 (2020). MSC: 68-XX 65-XX PDFBibTeX XMLCite \textit{P. Alexandersson} and \textit{P. Restadh}, Lect. Notes Comput. Sci. 11989, 333--338 (2020; Zbl 07441080) Full Text: DOI arXiv
Poureidi, Abolfazl; Jafari Rad, Nader On algorithmic complexity of double Roman domination. (English) Zbl 1453.05093 Discrete Appl. Math. 285, 539-551 (2020). Reviewer: Venkatakrishnan Yanamandram (Tiruchirappalli) MSC: 05C69 PDFBibTeX XMLCite \textit{A. Poureidi} and \textit{N. Jafari Rad}, Discrete Appl. Math. 285, 539--551 (2020; Zbl 1453.05093) Full Text: DOI
Döcker, Janosch; Dorn, Britta; Linz, Simone; Semple, Charles Placing quantified variants of 3-SAT and not-all-equal 3-SAT in the polynomial hierarchy. (English) Zbl 1440.68114 Theor. Comput. Sci. 822, 72-91 (2020). MSC: 68Q25 03B70 68Q17 68R07 PDFBibTeX XMLCite \textit{J. Döcker} et al., Theor. Comput. Sci. 822, 72--91 (2020; Zbl 1440.68114) Full Text: DOI arXiv
Poureidi, Abolfazl; Rad, Nader Jafari Algorithmic and complexity aspects of problems related to total Roman domination for graphs. (English) Zbl 1462.05284 J. Comb. Optim. 39, No. 3, 747-763 (2020). Reviewer: Seyed Mahmood Sheikholeslami (Tabriz) MSC: 05C69 05C85 68Q25 PDFBibTeX XMLCite \textit{A. Poureidi} and \textit{N. J. Rad}, J. Comb. Optim. 39, No. 3, 747--763 (2020; Zbl 1462.05284) Full Text: DOI
Eppstein, David; Goodrich, Michael T.; Liu, James A.; Matias, Pedro Tracking paths in planar graphs. (English) Zbl 07650287 Lu, Pinyan (ed.) et al., 30th international symposium on algorithms and computation, ISAAC 2019, Shanghai University of Finance and Economics, Shanghai, China, December 8–11, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 149, Article 54, 17 p. (2019). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Eppstein} et al., LIPIcs -- Leibniz Int. Proc. Inform. 149, Article 54, 17 p. (2019; Zbl 07650287) Full Text: DOI arXiv
Ahadi, Arash; Dehghan, Ali (2/2/3)-SAT problem and its applications in dominating set problems. (English) Zbl 1430.05031 Discrete Math. Theor. Comput. Sci. 21, No. 4, Paper No. 9, 10 p. (2019). MSC: 05C15 05C69 68Q17 90C27 PDFBibTeX XMLCite \textit{A. Ahadi} and \textit{A. Dehghan}, Discrete Math. Theor. Comput. Sci. 21, No. 4, Paper No. 9, 10 p. (2019; Zbl 1430.05031) Full Text: arXiv Link
Rad, Nader Jafari On the complexity of multiple bondage in graphs. (English) Zbl 1435.05157 Theor. Comput. Sci. 796, 180-186 (2019). MSC: 05C69 68Q17 PDFBibTeX XMLCite \textit{N. J. Rad}, Theor. Comput. Sci. 796, 180--186 (2019; Zbl 1435.05157) Full Text: DOI
Pilz, Alexander Planar 3-SAT with a clause/variable cycle. (English) Zbl 1417.05040 Discrete Math. Theor. Comput. Sci. 21, No. 3, Paper No. 18, 20 p. (2019). MSC: 05C10 05C38 05C45 68T20 68R10 68Q17 PDFBibTeX XMLCite \textit{A. Pilz}, Discrete Math. Theor. Comput. Sci. 21, No. 3, Paper No. 18, 20 p. (2019; Zbl 1417.05040) Full Text: arXiv Link
Rusu, Irena Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT. (English) Zbl 1421.68088 Theor. Comput. Sci. 771, 23-38 (2019). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{I. Rusu}, Theor. Comput. Sci. 771, 23--38 (2019; Zbl 1421.68088) Full Text: DOI arXiv
Pilz, Alexander Planar 3-SAT with a clause/variable cycle. (English) Zbl 1477.68294 Eppstein, David (ed.), 16th Scandinavian symposium and workshops on algorithm theory. SWAT 2018, June 18–20, 2018, Malmö University, Malmö, Sweden. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 101, Article 31, 13 p. (2018). MSC: 68T20 05C10 05C45 68Q25 68R10 PDFBibTeX XMLCite \textit{A. Pilz}, LIPIcs -- Leibniz Int. Proc. Inform. 101, Article 31, 13 p. (2018; Zbl 1477.68294) Full Text: DOI
Dehghan, Ali; Sadeghi, Mohammad-Reza; Ahadi, Arash Sigma partitioning: complexity and random graphs. (English) Zbl 1403.05118 Discrete Math. Theor. Comput. Sci. 20, No. 2, Paper No. 19, 14 p. (2018). MSC: 05C70 05C78 05C15 05C80 68Q17 PDFBibTeX XMLCite \textit{A. Dehghan} et al., Discrete Math. Theor. Comput. Sci. 20, No. 2, Paper No. 19, 14 p. (2018; Zbl 1403.05118) Full Text: arXiv Link
Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina Selecting and covering colored points. (English) Zbl 1398.05212 Discrete Appl. Math. 250, 75-86 (2018). MSC: 05D10 68W25 68U05 68Q17 PDFBibTeX XMLCite \textit{E. M. Arkin} et al., Discrete Appl. Math. 250, 75--86 (2018; Zbl 1398.05212) Full Text: DOI
Henning, Michael A.; Yeo, Anders Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs. (English) Zbl 1388.05185 Discrete Math. 341, No. 8, 2285-2292 (2018). MSC: 05D15 05C15 05C65 PDFBibTeX XMLCite \textit{M. A. Henning} and \textit{A. Yeo}, Discrete Math. 341, No. 8, 2285--2292 (2018; Zbl 1388.05185) Full Text: DOI
Döcker, Janosch; Linz, Simone On the existence of a cherry-picking sequence. (English) Zbl 1386.68111 Theor. Comput. Sci. 714, 36-50 (2018). MSC: 68R05 68Q17 68Q25 68Q45 92D15 PDFBibTeX XMLCite \textit{J. Döcker} and \textit{S. Linz}, Theor. Comput. Sci. 714, 36--50 (2018; Zbl 1386.68111) Full Text: DOI arXiv
Prunescu, Mihai About a surprising computer program of Matthias Müller. (English) Zbl 1420.68100 Adiprasito, Karim (ed.) et al., Convexity and discrete geometry including graph theory. Mulhouse, France, September 1–11, 2014. Cham: Springer. Springer Proc. Math. Stat. 148, 97-108 (2016). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{M. Prunescu}, Springer Proc. Math. Stat. 148, 97--108 (2016; Zbl 1420.68100) Full Text: DOI
Dehghan, Ali; Sadeghi, Mohammad-Reza; Ahadi, Arash On the complexity of deciding whether the regular number is at most two. (English) Zbl 1321.05082 Graphs Comb. 31, No. 5, 1359-1365 (2015). MSC: 05C15 05C20 68Q25 PDFBibTeX XMLCite \textit{A. Dehghan} et al., Graphs Comb. 31, No. 5, 1359--1365 (2015; Zbl 1321.05082) Full Text: DOI arXiv
Attali, Dominique; Bauer, Ulrich; Devillers, Olivier; Glisse, Marc; Lieutier, André Homological reconstruction and simplification in \(\mathbb{R}^3\). (English) Zbl 1326.55006 Comput. Geom. 48, No. 8, 606-621 (2015). Reviewer: Jonathan Hodgson (Swarthmore) MSC: 55N35 57M99 57Q99 55U10 68Q25 PDFBibTeX XMLCite \textit{D. Attali} et al., Comput. Geom. 48, No. 8, 606--621 (2015; Zbl 1326.55006) Full Text: DOI
Araujo, Julio; Nisse, Nicolas; Pérennes, Stéphane Weighted coloring in trees. (English) Zbl 1359.68115 Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 75-86 (2014). MSC: 68Q25 05C05 05C15 05C22 05C85 PDFBibTeX XMLCite \textit{J. Araujo} et al., LIPIcs -- Leibniz Int. Proc. Inform. 25, 75--86 (2014; Zbl 1359.68115) Full Text: DOI
Rajan, Bharati; Rajasingh, Indra; Cynthia, Jude Annie; Manuel, Paul Metric dimension of directed graphs. (English) Zbl 1305.05090 Int. J. Comput. Math. 91, No. 7, 1397-1406 (2014). MSC: 05C20 05C05 05C10 05C12 05C85 68Q17 PDFBibTeX XMLCite \textit{B. Rajan} et al., Int. J. Comput. Math. 91, No. 7, 1397--1406 (2014; Zbl 1305.05090) Full Text: DOI
Müller, Sebastian; Tzameret, Iddo Short propositional refutations for dense random 3CNF formulas. (English) Zbl 1391.03042 Ann. Pure Appl. Logic 165, No. 12, 1864-1918 (2014). MSC: 03F20 03D15 03F30 03B05 68Q25 PDFBibTeX XMLCite \textit{S. Müller} and \textit{I. Tzameret}, Ann. Pure Appl. Logic 165, No. 12, 1864--1918 (2014; Zbl 1391.03042) Full Text: DOI
Hertli, Timon 3-SAT faster and simpler – unique-SAT bounds for PPSZ hold in general. (English) Zbl 1297.68216 SIAM J. Comput. 43, No. 2, 718-729 (2014). MSC: 68T20 68Q25 68R05 68W20 PDFBibTeX XMLCite \textit{T. Hertli}, SIAM J. Comput. 43, No. 2, 718--729 (2014; Zbl 1297.68216) Full Text: DOI arXiv
Ahadi, A.; Dehghan, A. The complexity of the proper orientation number. (English) Zbl 1284.68286 Inf. Process. Lett. 113, No. 19-21, 799-803 (2013). MSC: 68Q25 05C15 05C10 PDFBibTeX XMLCite \textit{A. Ahadi} and \textit{A. Dehghan}, Inf. Process. Lett. 113, No. 19--21, 799--803 (2013; Zbl 1284.68286) Full Text: DOI arXiv
Makino, Kazuhisa; Tamaki, Suguru; Yamamoto, Masaki Derandomizing the HSSW algorithm for 3-SAT. (English) Zbl 1277.68097 Algorithmica 67, No. 2, 112-124 (2013). MSC: 68Q25 68W40 68W20 PDFBibTeX XMLCite \textit{K. Makino} et al., Algorithmica 67, No. 2, 112--124 (2013; Zbl 1277.68097) Full Text: DOI arXiv
Müller, Sebastian; Tzameret, Iddo Short propositional refutations for dense random 3CNF formulas. (English) Zbl 1364.03082 Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25–28, 2012. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4769-5). 501-510 (2012). MSC: 03F20 03B05 PDFBibTeX XMLCite \textit{S. Müller} and \textit{I. Tzameret}, in: Proceedings of the 2012 27th annual ACM/IEEE symposium on logic in computer science, LICS 2012, Dubrovnik, Croatia, June 25--28, 2012. Los Alamitos, CA: IEEE Computer Society. 501--510 (2012; Zbl 1364.03082) Full Text: DOI
Brun, Yuriy Efficient 3-SAT algorithms in the tile assembly model. (English) Zbl 1362.68100 Nat. Comput. 11, No. 2, 209-229 (2012). MSC: 68Q25 68Q05 68Q10 PDFBibTeX XMLCite \textit{Y. Brun}, Nat. Comput. 11, No. 2, 209--229 (2012; Zbl 1362.68100) Full Text: DOI
De Berg, Mark; Khosravi, Amirali Optimal binary space partitions for segments in the plane. (English) Zbl 1267.68268 Int. J. Comput. Geom. Appl. 22, No. 3, 187-205 (2012). MSC: 68U05 68Q17 PDFBibTeX XMLCite \textit{M. De Berg} and \textit{A. Khosravi}, Int. J. Comput. Geom. Appl. 22, No. 3, 187--205 (2012; Zbl 1267.68268) Full Text: DOI
Ilinca, L.; Kahn, J. The number of 3-SAT functions. (English) Zbl 1258.68104 Isr. J. Math. 192, Part B, 869-919 (2012). MSC: 68R10 68Q25 05C05 05C30 06E30 PDFBibTeX XMLCite \textit{L. Ilinca} and \textit{J. Kahn}, Isr. J. Math. 192, Part B, 869--919 (2012; Zbl 1258.68104) Full Text: DOI arXiv
Dupuis, Paul; Kaynar, Bahar; Ridder, Ad; Rubinstein, Reuven; Vaisman, Radislav Counting with combined splitting and capture–recapture methods. (English) Zbl 1254.65010 Stoch. Models 28, No. 3, 478-502 (2012). MSC: 65C05 65C35 68W20 60C05 PDFBibTeX XMLCite \textit{P. Dupuis} et al., Stoch. Models 28, No. 3, 478--502 (2012; Zbl 1254.65010) Full Text: DOI arXiv
Bang-Jensen, Jørgen; Havet, Frédéric; Trotignon, Nicolas Finding an induced subdivision of a digraph. (English) Zbl 1243.68190 Theor. Comput. Sci. 443, 10-24 (2012). MSC: 68Q25 68Q17 05C20 05C38 PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., Theor. Comput. Sci. 443, 10--24 (2012; Zbl 1243.68190) Full Text: DOI arXiv
Mahajan, Meena; Nimbhorkar, Prajakta; Varadarajan, Kasturi The planar \(k\)-means problem is NP-hard. (English) Zbl 1260.68158 Theor. Comput. Sci. 442, 13-21 (2012). Reviewer: Abbas Mehrabian (Waterloo) MSC: 68Q17 68U05 05C10 PDFBibTeX XMLCite \textit{M. Mahajan} et al., Theor. Comput. Sci. 442, 13--21 (2012; Zbl 1260.68158) Full Text: DOI
Alamdari, Soroush; Mehrabian, Abbas On a DAG partitioning problem. (English) Zbl 1342.05109 Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 9th international workshop, WAW 2012, Halifax, NS, Canada, June 22–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30540-5/pbk). Lecture Notes in Computer Science 7323, 17-28 (2012). MSC: 05C70 05C82 05C12 05C22 05C40 05C20 68Q25 PDFBibTeX XMLCite \textit{S. Alamdari} and \textit{A. Mehrabian}, Lect. Notes Comput. Sci. 7323, 17--28 (2012; Zbl 1342.05109) Full Text: DOI
Bondarenko, V. A.; Nikolaev, A. V. A class of hypergraphs and vertices of cut polytope relaxations. (English. Russian original) Zbl 1244.05157 Dokl. Math. 85, No. 1, 46-47 (2012); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 442, No. 3, 300-302 (2012). MSC: 05C65 52B99 PDFBibTeX XMLCite \textit{V. A. Bondarenko} and \textit{A. V. Nikolaev}, Dokl. Math. 85, No. 1, 46--47 (2012; Zbl 1244.05157); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 442, No. 3, 300--302 (2012) Full Text: DOI
Hertli, Timon; Moser, Robin A.; Scheder, Dominik Improving PPSZ for 3-SAT using critical variables. (English) Zbl 1230.68179 Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 237-248, electronic only (2011). MSC: 68T20 68W20 68W40 PDFBibTeX XMLCite \textit{T. Hertli} et al., LIPIcs -- Leibniz Int. Proc. Inform. 9, 237--248 (2011; Zbl 1230.68179) Full Text: DOI arXiv Link
Chin, Francis Y. L.; Guo, Zeyu; Sun, He Minimum Manhattan network is NP-complete. (English) Zbl 1228.05185 Discrete Comput. Geom. 45, No. 4, 701-722 (2011). MSC: 05C35 05C12 PDFBibTeX XMLCite \textit{F. Y. L. Chin} et al., Discrete Comput. Geom. 45, No. 4, 701--722 (2011; Zbl 1228.05185) Full Text: DOI
Chaudhari, Narendra S. Improved polynomial algorithm for 3-SAT. (English) Zbl 1242.68112 J. Indian Acad. Math. 32, No. 1, 251-267 (2010). MSC: 68Q17 68T20 PDFBibTeX XMLCite \textit{N. S. Chaudhari}, J. Indian Acad. Math. 32, No. 1, 251--267 (2010; Zbl 1242.68112)
Dantsin, Evgeny Maximum satisfiability and subexponential time. (English) Zbl 1220.68061 Feferman, Solomon (ed.) et al., Proofs, categories and computations. Essays in honor of Grigori Mints. With the collaboration of Vladik Kreinovich, Vladimir Lifschitz, and Ruy de Queiroz. London: College Publications (ISBN 978-1-84890-012-7/pbk). Tributes 13, 81-91 (2010). MSC: 68Q25 PDFBibTeX XMLCite \textit{E. Dantsin}, Tributes 13, 81--91 (2010; Zbl 1220.68061)
Iwama, Kazuo; Seto, Kazuhisa; Takai, Tadashi; Tamaki, Suguru Improved randomized algorithms for 3-SAT. (English) Zbl 1310.68230 Cheong, Otfried (ed.) et al., Algorithms and computation. 21st international symposium, ISAAC 2010, Jeju Island, Korea, December 15–17, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-17516-9/pbk). Lecture Notes in Computer Science 6506, 73-84 (2010). MSC: 68W20 68Q25 PDFBibTeX XMLCite \textit{K. Iwama} et al., Lect. Notes Comput. Sci. 6506, 73--84 (2010; Zbl 1310.68230) Full Text: DOI
Matsuki, Norichika A numerical approach to 3-SAT. (English) Zbl 1191.65004 Adv. Comput. Sci. Eng. 4, No. 1, 89-92 (2010). Reviewer: Vassil Grozdanov (Blagoevgrad) MSC: 65C05 11K45 PDFBibTeX XMLCite \textit{N. Matsuki}, Adv. Comput. Sci. Eng. 4, No. 1, 89--92 (2010; Zbl 1191.65004) Full Text: Link
Chin, Francis Y. L.; Guo, Zeyu; Sun, He Minimum Manhattan network is NP-complete. (English) Zbl 1388.68287 Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 393-402 (2009). MSC: 68U05 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{F. Y. L. Chin} et al., in: Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8--10, 2009. New York, NY: Association for Computing Machinery (ACM). 393--402 (2009; Zbl 1388.68287) Full Text: DOI Link
Chaudhari, Narendra S. Computationally hard problems: 3-SAT and its polynomial solvability. (English) Zbl 1247.68107 J. Indian Acad. Math. 31, No. 2, 407-444 (2009). MSC: 68Q25 68T20 PDFBibTeX XMLCite \textit{N. S. Chaudhari}, J. Indian Acad. Math. 31, No. 2, 407--444 (2009; Zbl 1247.68107)
Díaz, Josep; Kirousis, Lefteris; Mitsche, Dieter; Pérez-Giménez, Xavier A new upper bound for 3-SAT. (English) Zbl 1248.68242 Hariharan, Ramesh (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2008), December 9–11, 2008, Bangalore, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-08-8). LIPIcs – Leibniz International Proceedings in Informatics 2, 163-174, electronic only (2008). MSC: 68Q25 68T20 68Q87 PDFBibTeX XMLCite \textit{J. Díaz} et al., LIPIcs -- Leibniz Int. Proc. Inform. 2, 163--174 (2008; Zbl 1248.68242) Full Text: DOI Link
Ishdorj, Tseren-Onolt; Leporati, Alberto Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. (English) Zbl 1187.68239 Nat. Comput. 7, No. 4, 519-534 (2008). MSC: 68Q10 68T05 PDFBibTeX XMLCite \textit{T.-O. Ishdorj} and \textit{A. Leporati}, Nat. Comput. 7, No. 4, 519--534 (2008; Zbl 1187.68239) Full Text: DOI
Brun, Yuriy Solving satisfiability in the tile assembly model with a constant-size tileset. (English) Zbl 1162.68446 J. Algorithms 63, No. 4, 151-166 (2008). MSC: 68Q10 68T20 PDFBibTeX XMLCite \textit{Y. Brun}, J. Algorithms 63, No. 4, 151--166 (2008; Zbl 1162.68446) Full Text: DOI
Maneva, Elitza; Sinclair, Alistair On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. (English) Zbl 1152.68052 Theor. Comput. Sci. 407, No. 1-3, 359-369 (2008). MSC: 68T20 PDFBibTeX XMLCite \textit{E. Maneva} and \textit{A. Sinclair}, Theor. Comput. Sci. 407, No. 1--3, 359--369 (2008; Zbl 1152.68052) Full Text: DOI
Jia, H.; Moore, Cristopher; Strain, D. Generating hard satisfiable formulas by hiding solutions deceptively. (English) Zbl 1182.68249 J. Artif. Intell. Res. (JAIR) 28, 107-118 (2007). MSC: 68T20 PDFBibTeX XMLCite \textit{H. Jia} et al., J. Artif. Intell. Res. (JAIR) 28, 107--118 (2007; Zbl 1182.68249)
Leporati, Alberto; Felloni, Sara Three “quantum” algorithms to solve 3-SAT. (English) Zbl 1111.68041 Theor. Comput. Sci. 372, No. 2-3, 218-241 (2007). MSC: 68Q10 81P68 68T20 PDFBibTeX XMLCite \textit{A. Leporati} and \textit{S. Felloni}, Theor. Comput. Sci. 372, No. 2--3, 218--241 (2007; Zbl 1111.68041) Full Text: DOI Link
Cheng, Sheng-Tzong; Tao, Ming-Hung Quantum cooperative search algorithm for 3-sat. (English) Zbl 1178.68182 J. Comput. Syst. Sci. 73, No. 1, 123-136 (2007). MSC: 68P10 68W05 PDFBibTeX XMLCite \textit{S.-T. Cheng} and \textit{M.-H. Tao}, J. Comput. Syst. Sci. 73, No. 1, 123--136 (2007; Zbl 1178.68182) Full Text: DOI
Leporati, Alberto; Zandron, Claudio; Gutiérrez-Naranjo, Miguel A. P systems with input in binary form. (English) Zbl 1088.68059 Int. J. Found. Comput. Sci. 17, No. 1, 127-146 (2006). MSC: 68Q10 68Q17 PDFBibTeX XMLCite \textit{A. Leporati} et al., Int. J. Found. Comput. Sci. 17, No. 1, 127--146 (2006; Zbl 1088.68059) Full Text: DOI
Lozinskii, Eliezer L. Another look at the phenomenon of phase transition. (English) Zbl 1101.68843 J. Exp. Theor. Artif. Intell. 17, No. 3, 243-266 (2005). MSC: 68T20 68R10 PDFBibTeX XMLCite \textit{E. L. Lozinskii}, J. Exp. Theor. Artif. Intell. 17, No. 3, 243--266 (2005; Zbl 1101.68843) Full Text: DOI
van Maaren, Hans; van Norden, Linda Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances. (English) Zbl 1099.68104 Ann. Math. Artif. Intell. 44, No. 1-2, 157-177 (2005). MSC: 68T20 68T15 68T27 PDFBibTeX XMLCite \textit{H. van Maaren} and \textit{L. van Norden}, Ann. Math. Artif. Intell. 44, No. 1--2, 157--177 (2005; Zbl 1099.68104) Full Text: DOI
van Maaren, Hans; van Norden, Linda Hidden threshold phenomena for fixed-density SAT-formulae. (English) Zbl 1204.68214 Giunchiglia, Enrico (ed.) et al., Theory and applications of satisfiability testing. 6th international conference, SAT 2003, Santa Margherita Ligure, Italy, May 5–8, 2003. Selected revised papers. Berlin: Springer (ISBN 3-540-20851-8/pbk). Lect. Notes Comput. Sci. 2919, 135-149 (2004). MSC: 68T20 05C15 PDFBibTeX XMLCite \textit{H. van Maaren} and \textit{L. van Norden}, Lect. Notes Comput. Sci. 2919, 135--149 (2004; Zbl 1204.68214) Full Text: DOI
Brueggemann, Tobias; Kern, Walter An improved local search algorithm for 3-SAT. (English) Zbl 1152.68544 Liberti, Leo (ed.) et al., Workshop on graphs and combinatorial optimization. Papers from the workshop, Como, Italy, May 31, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 17, 69-73 (2004). MSC: 68T20 90B40 68W25 PDFBibTeX XMLCite \textit{T. Brueggemann} and \textit{W. Kern}, Electron. Notes Discrete Math. 17, 69--73 (2004; Zbl 1152.68544) Full Text: DOI Link
Brueggemann, Tobias; Kern, Walter An improved deterministic local search algorithm for 3-SAT. (English) Zbl 1086.68051 Theor. Comput. Sci. 329, No. 1-3, 303-313 (2004). MSC: 68Q25 68W05 PDFBibTeX XMLCite \textit{T. Brueggemann} and \textit{W. Kern}, Theor. Comput. Sci. 329, No. 1--3, 303--313 (2004; Zbl 1086.68051) Full Text: DOI
Shang, Yi; Fromherz, Markus P. J. Experimental complexity analysis of continuous constraint satisfaction problems. (English) Zbl 1069.68601 Inf. Sci. 153, 1-36 (2003). MSC: 68T20 90C27 PDFBibTeX XMLCite \textit{Y. Shang} and \textit{M. P. J. Fromherz}, Inf. Sci. 153, 1--36 (2003; Zbl 1069.68601) Full Text: DOI
Fiorini, Samuel A combinatorial study of partial order polytopes. (English) Zbl 1020.52010 Eur. J. Comb. 24, No. 2, 149-159 (2003). Reviewer: Horst Martini (Chemnitz) MSC: 52B55 PDFBibTeX XMLCite \textit{S. Fiorini}, Eur. J. Comb. 24, No. 2, 149--159 (2003; Zbl 1020.52010) Full Text: DOI
Rhodes, David L.; Wolf, Wayne Two coNP-complete schedule analysis problems. (English) Zbl 1319.68044 Int. J. Found. Comput. Sci. 12, No. 5, 565-580 (2001). MSC: 68M20 68Q17 68Q25 90B35 PDFBibTeX XMLCite \textit{D. L. Rhodes} and \textit{W. Wolf}, Int. J. Found. Comput. Sci. 12, No. 5, 565--580 (2001; Zbl 1319.68044) Full Text: DOI
Sorkin, Gregory B. Some notes on random satisfiability. (English) Zbl 1054.68141 Steinhöfel, Kathleen (ed.), Stochastic algorithms: Foundations and applications. International symposium, SAGA 2001, Berlin, Germany, December 13–14, 2001. Proceedings. Berlin: Springer (ISBN 3-540-43025-3). Lect. Notes Comput. Sci. 2264, 117-130 (2001). MSC: 68T20 68W20 68W40 PDFBibTeX XMLCite \textit{G. B. Sorkin}, Lect. Notes Comput. Sci. 2264, 117--130 (2001; Zbl 1054.68141) Full Text: Link
Achlioptas, D. Lower bounds for random 3-SAT via differential equations. (English) Zbl 0983.68079 Theor. Comput. Sci. 265, No. 1-2, 159-185 (2001). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{D. Achlioptas}, Theor. Comput. Sci. 265, No. 1--2, 159--185 (2001; Zbl 0983.68079) Full Text: DOI
Kaporis, Alexis C.; Kirousis, Lefteris M.; Stamatiou, Yannis C.; Vamvakari, Malvina; Zito, Michele The unsatisfiability threshold revisited. (English) Zbl 0990.90557 Kautz, Henry (ed.) et al., LICS 2001 workshop on theory and application of satisfiability testing (SAT 2001). Boston, MA, USA, June 14-15, 2001. Amsterdam: Elsevier, Electron. Notes Discrete Math. 9, no pag., electronic only (2001). MSC: 90C27 90B80 PDFBibTeX XMLCite \textit{A. C. Kaporis} et al., Electron. Notes Discrete Math. 9, no pag. (2001; Zbl 0990.90557)
Le Berre, Daniel Exploiting the real power of unit propagation lookahead. (English) Zbl 0990.90538 Kautz, Henry (ed.) et al., LICS 2001 workshop on theory and application of satisfiability testing (SAT 2001). Boston, MA, USA, June 14-15, 2001. Amsterdam: Elsevier, Electron. Notes Discrete Math. 9, no pag., electronic only (2001). MSC: 90C27 PDFBibTeX XMLCite \textit{D. Le Berre}, Electron. Notes Discrete Math. 9, no pag. (2001; Zbl 0990.90538)
Cocco, Simona; Monasson, Remi Statistical physics analysis of the backtrack resolution of random 3-SAT instances. (English) Zbl 0994.90513 Kautz, Henry (ed.) et al., LICS 2001 workshop on theory and application of satisfiability testing (SAT 2001). Boston, MA, USA, June 14-15, 2001. Amsterdam: Elsevier, Electron. Notes Discrete Math. 9, no pag., electronic only (2001). MSC: 90C27 PDFBibTeX XMLCite \textit{S. Cocco} and \textit{R. Monasson}, Electron. Notes Discrete Math. 9, no pag. (2001; Zbl 0994.90513)
Janson, Svante; Stamatiou, Yannis C.; Vamvakari, Malvina Bounding the unsatisfiability threshold of random 3-SAT. (English) Zbl 0958.03028 Random Struct. Algorithms 17, No. 2, 103-116 (2000); erratum ibid. 18, No. 1, 99-100 (2001). MSC: 03D15 68Q25 03B05 60C05 PDFBibTeX XMLCite \textit{S. Janson} et al., Random Struct. Algorithms 17, No. 2, 103--116 (2000; Zbl 0958.03028) Full Text: DOI
Dubois, Olivier; Boufkhad, Yacine; Mandler, Jacques Typical random 3-SAT formulae and the satisfiability threshold. (English) Zbl 0959.68135 Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 126-127 (2000). MSC: 68W05 68Q05 PDFBibTeX XMLCite \textit{O. Dubois} et al., in: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, SODA 2000, San Francisco, CA, USA, January 9--11, 2000. Philadelphia, PA: SIAM. 126--127 (2000; Zbl 0959.68135)
Yoshida, Hiroshi; Suyama, Akira Solution to 3-SAT by breadth first search. (English) Zbl 0971.68062 Winfree, Erik (ed.) et al., DNA based computers V. DIMACS workshop, Massachusetts Institute of Technology, Cambridge, MA, USA, June 14-15, 1999. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 54, 9-22 (1999). MSC: 68Q10 68P10 68W10 PDFBibTeX XMLCite \textit{H. Yoshida} and \textit{A. Suyama}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 54, 9--22 (1999; Zbl 0971.68062)
Kullmann, O. New methods for 3-SAT decision and worst-case analysis. (English) Zbl 0930.68066 Theor. Comput. Sci. 223, No. 1-2, 1-72 (1999). MSC: 68Q25 PDFBibTeX XMLCite \textit{O. Kullmann}, Theor. Comput. Sci. 223, No. 1--2, 1--72 (1999; Zbl 0930.68066) Full Text: DOI
Kirousis, Lefteris M.; Kranakis, Evangelos; Krizanc, Danny; Stamatiou, Yannis C. Approximating the unsatisfiability threshold of random formulas. (English) Zbl 0936.68038 Random Struct. Algorithms 12, No. 3, 253-269 (1998). MSC: 68Q05 PDFBibTeX XMLCite \textit{L. M. Kirousis} et al., Random Struct. Algorithms 12, No. 3, 253--269 (1998; Zbl 0936.68038) Full Text: DOI
Chazelle, Bernard; Dobkin, David P.; Shouraboura, Nadia; Tal, Ayellet Strategies for polyhedral surface decomposition: an experimental study. (English) Zbl 1133.52305 Comput. Geom. 7, No. 5-6, 327-342 (1997). MSC: 52B55 68U05 PDFBibTeX XMLCite \textit{B. Chazelle} et al., Comput. Geom. 7, No. 5--6, 327--342 (1997; Zbl 1133.52305) Full Text: DOI Backlinks: MO
Kullmann, Oliver Worst-case analysis, 3-SAT decision and lower bounds: Approaches for improved SAT algorithms. (English) Zbl 0889.03030 Du, Dingzhu (ed.) et al., Satisfiability problem: theory and applications. DIMACS workshop, Piscataway, NJ, USA, March 11-13, 1996. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 35, 261-313 (1997). MSC: 03D15 68Q25 03B05 03B35 PDFBibTeX XMLCite \textit{O. Kullmann}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 35, 261--313 (1997; Zbl 0889.03030)
Zhang, Wenhui Number of models and satisfiability of sets of clauses. (English) Zbl 0873.68094 Theor. Comput. Sci. 155, No. 1, 277-288 (1996). MSC: 68Q25 03B05 03D15 PDFBibTeX XMLCite \textit{W. Zhang}, Theor. Comput. Sci. 155, No. 1, 277--288 (1996; Zbl 0873.68094) Full Text: DOI
Schrag, Robert; Crawford, James M. Implicates and prime implicates in random 3-SAT. (English) Zbl 1508.68345 Artif. Intell. 81, No. 1-2, 199-222 (1996). MSC: 68T20 03B05 68Q87 PDFBibTeX XMLCite \textit{R. Schrag} and \textit{J. M. Crawford}, Artif. Intell. 81, No. 1--2, 199--222 (1996; Zbl 1508.68345) Full Text: DOI
Freeman, Jon W. Hard random 3-SAT problems and the Davis-Putnam procedure. (English) Zbl 1508.68131 Artif. Intell. 81, No. 1-2, 183-198 (1996). MSC: 68Q25 68Q17 68T20 PDFBibTeX XMLCite \textit{J. W. Freeman}, Artif. Intell. 81, No. 1--2, 183--198 (1996; Zbl 1508.68131) Full Text: DOI
Crawford, James M.; Auton, Larry D. Experimental results on the crossover point in random 3-SAT. (English) Zbl 1508.68324 Artif. Intell. 81, No. 1-2, 31-57 (1996). MSC: 68T20 68Q87 PDFBibTeX XMLCite \textit{J. M. Crawford} and \textit{L. D. Auton}, Artif. Intell. 81, No. 1--2, 31--57 (1996; Zbl 1508.68324) Full Text: DOI
Brightwell, Graham; Winkler, Peter Counting linear extensions. (English) Zbl 0759.06001 Order 8, No. 3, 225-242 (1991). Reviewer: C.Masalagiu (Iaşi) MSC: 06A07 68Q25 68R05 PDFBibTeX XMLCite \textit{G. Brightwell} and \textit{P. Winkler}, Order 8, No. 3, 225--242 (1991; Zbl 0759.06001) Full Text: DOI
Iwanowski, Sebastian Testing approximate symmetry in the plane is NP-hard. (English) Zbl 0755.68068 Mathematical foundations of computer science, Proc. 14th Symp., MFCS ’89, Porąbka-Kozubnik/Pol. 1989, Lect. Notes Comput. Sci. 379, 291-304 (1989). MSC: 68Q25 68R99 PDFBibTeX XMLCite \textit{S. Iwanowski}, Lect. Notes Comput. Sci. None, 291--304 (1989; Zbl 0755.68068)
Chao, Ming-Te; Franco, John Probabilistic analysis of two heuristics for the 3-satisfiability problem. (English) Zbl 0621.68031 SIAM J. Comput. 15, 1106-1118 (1986). MSC: 68Q25 PDFBibTeX XMLCite \textit{M.-T. Chao} and \textit{J. Franco}, SIAM J. Comput. 15, 1106--1118 (1986; Zbl 0621.68031) Full Text: DOI Link
Vergis, Anastasios; Steiglitz, Kenneth; Dickinson, Bradley The complexity of analog computation. (English) Zbl 0594.68040 Math. Comput. Simulation 28, 91-113 (1986). MSC: 68Q25 68N99 68U20 68Q05 PDFBibTeX XMLCite \textit{A. Vergis} et al., Math. Comput. Simul. 28, 91--113 (1986; Zbl 0594.68040) Full Text: DOI