Search results for "2SAT"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
112	M. Borschbach, A. Exeler	A Tabu history driven crossover operator design for memetic algorithm applied to Max-2SAT-problems.	GECCO	2008	DBLP DOI BibTeX RDF	Max-2SAT, tabu search, memetic algorithms
108	K. Subramani 0001	On Determining the Minimum Length, Tree-Like Resolution Refutation of 2SAT, and Extended 2SAT Formulas.	ASIAN	2002	DBLP DOI BibTeX RDF
100	Peter J. Stuckey, Lei Zheng	Improving GSAT Using 2SAT.	CP	2002	DBLP DOI BibTeX RDF
100	K. Subramani 0001	On Identifying Simple and Quantified Lattice Points in the 2SAT Polytope.	AISC	2002	DBLP DOI BibTeX RDF
94	K. Subramani 0001	Optimal length tree-like resolution refutations for 2SAT formulas.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	2SAT formulas, tree-like proofs, Resolution
63	Osamu Watanabe 0001, Masaki Yamamoto 0001	Average-Case Analysis for the MAX-2SAT Problem.	SAT	2006	DBLP DOI BibTeX RDF
63	Miroslav Chlebík, Janka Chlebíková	On Approximation Hardness of the Minimum 2SAT-DELETION Problem.	MFCS	2004	DBLP DOI BibTeX RDF
63	Peter J. Stuckey, Lei Zheng	Improving Nogood Recording Using 2SAT.	ICTAI	2003	DBLP DOI BibTeX RDF
63	Markus Bläser, Bodo Manthey	Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.	ISAAC	2002	DBLP DOI BibTeX RDF
56	Venkatesan Guruswami	On 2-Query Codeword Testing with Near-Perfect Completeness.	ISAAC	2006	DBLP DOI BibTeX RDF
52	Dorit S. Hochbaum, Anu Pathria	Approximating a generalization of MAX 2SAT and MIN 2SAT.	Discret. Appl. Math.	2000	DBLP DOI BibTeX RDF
44	Magnus Wahlström	A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances.	IWPEC	2008	DBLP DOI BibTeX RDF
44	Mistuo Motoki	Test Instance Generation for MAX 2SAT.	CP	2005	DBLP DOI BibTeX RDF
44	Cristina Bazgan, Wenceslas Fernandez de la Vega	A Polynomial Time Approximation Scheme for Dense MIN 2SAT.	FCT	1999	DBLP DOI BibTeX RDF
37	Kuen-Lin Yu, Chung-Shou Liao, D. T. Lee	Maximizing the Number of Independent Labels in the Plane.	FAW	2007	DBLP DOI BibTeX RDF
37	Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell	Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?	FOCS	2004	DBLP DOI BibTeX RDF
37	Carlos Ansótegui, Ramón Béjar, Alba Cabiscol, Felip Manyà	The Interface between P and NP in Signed CNF Formulas.	ISMVL	2004	DBLP DOI BibTeX RDF
31	Christos H. Papadimitriou	On Selecting a Satisfying Truth Assignment (Extended Abstract)	FOCS	1991	DBLP DOI BibTeX RDF	2SAT, satisfying truth assignment selection, natural generalizations, default preference, polynomial-time randomized algorithm, complexity, satisfiability, minimality, circumscription, selection criteria
26	Guillermo De Ita, José Raymundo Marcial-Romero, José Antonio Hernández Servín	A bottom-up algorithm for solving ♯2SAT.	Log. J. IGPL	2020	DBLP DOI BibTeX RDF
26	Marco A. López Medina, José Raymundo Marcial-Romero, Guillermo De Ita Luna, José Antonio Hernández Servín	A Linear Time Algorithm for Counting #2SAT on Series-Parallel Formulas.	MICAI (1)	2020	DBLP DOI BibTeX RDF
26	David Avis, Hans Raj Tiwary	Compact linear programs for 2SAT.	Eur. J. Comb.	2019	DBLP DOI BibTeX RDF
26	Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang 0002	Linear-Time Algorithm for Quantum 2SAT.	Theory Comput.	2018	DBLP DOI BibTeX RDF
26	Alice Paul, Matthias Poloczek, David P. Williamson	Simple Approximation Algorithms for Balanced MAX 2SAT.	Algorithmica	2018	DBLP DOI BibTeX RDF
26	Marco A. López Medina, José Raymundo Marcial-Romero, Guillermo De Ita Luna, Yolanda Moyao	A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas.	MCPR	2018	DBLP DOI BibTeX RDF
26	Guillermo De Ita, Pedro Bello 0001, Miguel Rodríguez 0001	The computation of #2SAT by a fixed-parameter tractable algorithm.	LANMR	2018	DBLP BibTeX RDF
26	Marco A. López Medina, José Raymundo Marcial-Romero, José Antonio Hernández Servín, Guillermo De Ita	Model counting for #2SAT problem in outerplanar graphs.	LANMR	2018	DBLP BibTeX RDF
26	M. A. López, José Raymundo Marcial-Romero, Guillermo De Ita Luna, Héctor A. Montes Venegas, Roberto Alejo	A Linear Time Algorithm for Solving #2SAT on Cactus Formulas.	CoRR	2017	DBLP BibTeX RDF
26	David Avis, Hans Raj Tiwary	Compact linear programs for 2SAT.	CoRR	2017	DBLP BibTeX RDF
26	Marco A. López Medina, José Raymundo Marcial-Romero, Guillermo De Ita, Rosa Maria Valdovinos	A Fast and Efficient Method for #2SAT via Graph Transformations.	MICAI (1)	2017	DBLP DOI BibTeX RDF
26	Josep Argelich, Ramón Béjar, Cèsar Fernández, Carles Mateu, Jordi Planes	On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes.	Ann. Math. Artif. Intell.	2016	DBLP DOI BibTeX RDF
26	Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang 0002	Linear Time Algorithm for Quantum 2SAT.	ICALP	2016	DBLP DOI BibTeX RDF
26	Alice Paul, Matthias Poloczek, David P. Williamson	Simple Approximation Algorithms for Balanced MAX 2SAT.	LATIN	2016	DBLP DOI BibTeX RDF
26	Marco A. López Medina, José Raymundo Marcial-Romero, Guillermo De Ita Luna, José Antonio Hernández Servín	Un algoritmo para calcular #2SAT.	Res. Comput. Sci.	2015	DBLP BibTeX RDF
26	Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang 0002	Linear time algorithm for quantum 2SAT.	CoRR	2015	DBLP BibTeX RDF
26	José Raymundo Marcial-Romero, Guillermo De Ita Luna, José Antonio Hernández Servín, Rosa Maria Valdovinos	A Parametric Polynomial Deterministic Algorithm for #2SAT.	MICAI (1)	2015	DBLP DOI BibTeX RDF
26	Nitin Salodkar, Subramanian Rajagopalan, Sambuddha Bhattacharya, Shabbir H. Batterywala	2SAT Based Infeasibility Resolution during Design Rule Correction on Layouts with Multiple Grids.	VLSID	2015	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, José Raymundo Marcial-Romero, Yolanda Moyao	An Enumerative Algorithm for #2SAT.	Electron. Notes Discret. Math.	2014	DBLP DOI BibTeX RDF
26	Alistair Sinclair, Dan Vilenchik	Delaying satisfiability for random 2SAT.	Random Struct. Algorithms	2013	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, Pedro Bello 0001, Meliza Contreras	Recognizing Structural Patterns on Graphs for the Efficient Computation of #2SAT.	MCPR	2013	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, José Raymundo Marcial-Romero	Computing #2SAT and #2UNSAT by Binary Patterns.	MCPR	2012	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, José Raymundo Marcial-Romero, José Antonio Hernández Servín	A Threshold for a Polynomial Solution of #2SAT.	Fundam. Informaticae	2011	DBLP DOI BibTeX RDF
26	Josep Argelich, Ramón Béjar, Cèsar Fernández, Carles Mateu	On 2SAT-MaxOnes with Unbalanced Polarity: from Easy Problems to Hard MaxClique Problems.	CCIA	2011	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, César Bautista, Luis Carlos Altamirano	Solving 3-Colouring via 2SAT.	MCPR	2011	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, Fernando Zacarías Flores, Alejandro Rangel-Huerta	A Note for Parametric Complexity of #2SAT.	LA-NMR	2011	DBLP BibTeX RDF
26	Osamu Watanabe 0001, Masaki Yamamoto 0001	Average-case analysis for the MAX-2SAT problem.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
26	Hans-Joachim Böckenhauer, Michal Forisek, Ján Oravec, Björn Steffen, Kathleen Steinhöfel, Monika Steinová	The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification.	RAIRO Theor. Informatics Appl.	2010	DBLP DOI BibTeX RDF
26	Alistair Sinclair, Dan Vilenchik	Delaying Satisfiability for Random 2SAT.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
26	Guillermo De Ita Luna, Pedro Bello López, Meliza Contreras González	New Polynomial Classes for #2SAT Established Via Graph-Topological Structure.	Eng. Lett.	2007	DBLP BibTeX RDF
26	Carlos Guillén, Aurelio López-López, Guillermo De Ita Luna	Model Counting for 2SAT Based on Graphs by Matrix Operators.	Eng. Lett.	2007	DBLP BibTeX RDF
26	Miroslav Chlebík, Janka Chlebíková	Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover.	Discret. Appl. Math.	2007	DBLP DOI BibTeX RDF
26	Pierre Bonami, Michel Minoux	Exact MAX-2SAT solution via lift-and-project closure.	Oper. Res. Lett.	2006	DBLP DOI BibTeX RDF
26	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Note on MAX 2SAT.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
26	Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström	Counting models for 2SAT and 3SAT formulae.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
26	K. Subramani 0001	On deciding the non-emptiness of 2SAT polytopes with respect to First Order Queries.	Math. Log. Q.	2004	DBLP DOI BibTeX RDF
26	Lei Zheng, Peter J. Stuckey	Improving SAT Using 2SAT.	ACSC	2002	DBLP BibTeX RDF
26	Hans van Maaren, Joost P. Warners	Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT.	Discret. Appl. Math.	2000	DBLP DOI BibTeX RDF
26	Maria Alberta Alberti, Alberto Bertoni, Paola Campadelli, Giuliano Grossi, Roberto Posenato	A Neural Algorithm for MAX-2SAT: Performance Analysis and Circuit Implementation.	Neural Networks	1997	DBLP DOI BibTeX RDF
26	Uriel Feige, Michel X. Goemans	Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.	ISTCS	1995	DBLP DOI BibTeX RDF
26	Michel X. Goemans, David P. Williamson	.879-approximation algorithms for MAX CUT and MAX 2SAT.	STOC	1994	DBLP DOI BibTeX RDF
19	K. Subramani 0001	Absorbing Random Walks and the NAE2SAT Problem.	FAW	2008	DBLP DOI BibTeX RDF
19	Vineet Bafna, Vikas Bansal 0001	Improved Recombination Lower Bounds for Haplotype Data.	RECOMB	2005	DBLP DOI BibTeX RDF
19	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
19	Ryan Williams 0001	On Computing k-CNF Formula Properties.	SAT	2003	DBLP DOI BibTeX RDF
19	Alon Efrat, Cesim Erten, Stephen G. Kobourov	Fixed-Location Circular-Arc Drawing of Planar Graphs.	GD	2003	DBLP DOI BibTeX RDF
19	Zhongping Qin, Binhai Zhu	A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels.	SWAT	2002	DBLP DOI BibTeX RDF
19	Alvaro del Val	Simplifying Binary Propositional Theories into Connected Components Twice as Fast.	LPAR	2001	DBLP DOI BibTeX RDF
19	Takao Asano, Magnús M. Halldórsson, Kazuo Iwama, Takeshi Matsuda	Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.	ISAAC	2000	DBLP DOI BibTeX RDF
19	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results (Extended Abstract).	ICALP	1999	DBLP DOI BibTeX RDF	Approximation Hardness, Bounded Dependency Satisfiability, Breakpoint Graphs, Node Cover, Approximation Algorithms, Independent Set, MAX-CUT, Sorting by Reversals
19	Howard J. Karloff, Uri Zwick	A 7/8-Approximation Algorithm for MAX 3SAT?	FOCS	1997	DBLP DOI BibTeX RDF
19	David P. Williamson	Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture).	WG	1997	DBLP DOI BibTeX RDF