Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

No abstract is available for this paper.

• Publication year

  1990

• Venue

  Information Sciences

• Publication date

  1990-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0020-0255(90)90030-E
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Probabilistic Performance of Algorithms for the Satisfiability Problem

  1986cited by this paper
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem

  1986cited by this paper
• The Pure Literal Rule and Polynomial Average Time

  1985cited by this paper
• Probabilistic analysis of the pure literal heuristic for the satisfiability problem

  1984cited by this paper
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

  1983cited by this paper
• Search Rearrangement Backtracking and Polynomial Average Time

  1983cited by this paper
• Average Time Analyses of Simplified Davis-Putnam Procedures

  1982cited by this paper
• An Average Time Analysis of Backtracking

  1981cited by this paper
• A Computing Procedure for Quantification Theory

  1960cited by this paper

• A technical note for the 91-clauses SAT resolution with Indirect QAOA based approach

  2024cites this paper
• Quantum hybrid algorithm for solving SAT problem

  2023cites this paper
• Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT

  2023cites this paper
• BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit

  2022cites this paper
• S ep 2 00 2 The Asymptotic Order of the Random kSAT Threshold

  2022cites this paper
• Incorporating Multi-armed Bandit with Local Search for MaxSAT

  2022cites this paper
• Handbook of Satisfiability

  2021cites this paper
• Solving Non-uniform Planted and Filtered Random SAT Formulas Greedily

  2021cites this paper
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

  2021cites this paper
• Results on a Super Strong Exponential Time Hypothesis

  2020cites this paper
• Faster Random k-CNF Satisfiability

  2019cites this paper
• Super solutions of random (3 + p)-SAT

  2019cites this paper
• CNF Encodings of Cardinality Constraints Based on Comparator Networks

  2019cites this paper
• On Super Strong ETH

  2019cites this paper
• Algorithms for the Satisfiability Problem

  2018cites this paper
• Super Strong ETH is False for Random k-SAT

  2018cites this paper
• Belief Propagation Guided Decimation Fails on Random Formulas

  2017cites this paper
• From Decimation to Local Search and Back: A New Approach to MaxSAT

  2017cites this paper
• Why does Lookahead work ?

  2017cites this paper
• Spectral Techniques in Argumentation Framework Analysis

  2016cites this paper
• Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas

  2016cites this paper
• Walksat Stalls Well Below Satisfiability

  2016cites this paper
• Resolution Complexity of Random Constraint Satisfaction Problems

  2016cites this paper
• Giant Component and Poisson Cloning Model

  2015cites this paper
• Probabilistic Analysis of Random Mixed Horn Formulas

  2014cites this paper
• Local techniques in quadratic optimization and Satisfiability, and their applications

  2014cites this paper
• Instability, Evolution and Morphogenesis

  2013cites this paper
• New approaches to integer programming

  2012cites this paper
• Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas

  2012influential citation
• Phase Transition in Random Integer Programs

  2012cites this paper
• The Power of Choice for Random Satisfiability

  2012cites this paper
• Appendix A: Symbols and Notations

  2012cites this paper
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

  2012cites this paper
• Integer feasibility of random polytopes: random integer programs

  2011cites this paper
• Boolean Functions

  2011cites this paper
• Measuring the Hardness of Stochastic Sampling on Bayesian Networks with Deterministic Causalities: the k-Test

  2011cites this paper
• Analyzing Walksat on Random Formulas

  2011cites this paper
• CS 271 Randomness & Computation Fall 2011 Lecture 7 : September 15

  2011cites this paper
• Integer Feasibility of Random Polytopes

  2011cites this paper
• On simple but hard random instances of propositional theories and logic programs

  2011cites this paper
• An algorithm for random signed 3-SAT with intervals

  2011cites this paper
• Poisson Cloning Model for Random Graphs Extended Abstract

  2010cites this paper
• Report on the Workshop on Satisfiability : Assessing the Progress

  2010cites this paper
• Probabilistic Analysis of Satisfiability Algorithms

  2010cites this paper
• On belief propagation guided decimation for random k-SAT

  2010cites this paper
• Theoretical analysis of practical heuristics for satisfiability

  2009cites this paper
• A Better Algorithm for Random k-SAT

  2009cites this paper
• Random Constraint Satisfaction Problems

  2009cites this paper
• On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas

  2009cites this paper
• Workshop on Satisfiability

  2009cites this paper
• CSP problems as algorithmic benchmarks: measures, methods and models

  2009cites this paper
• A History of Satisfiability

  2009cites this paper
• On smoothed k-CNF formulas and the Walksat algorithm

  2009cites this paper
• Finding cores of random 2-SAT formulae via Poisson cloning

  2008influential citation
• Expansion, Random Graphs and the Automatizability of Resolution

  2008cites this paper
• Poisson Cloning Model for Random Graphs

  2008cites this paper
• Chapter 8 Random Satisfiability

  2008cites this paper
• Threshold Phenomena in Random Constraint Satisfaction Problems

  2008cites this paper
• Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k

  2008cites this paper
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

  2007cites this paper
• Expected number of locally maximal solutions for random Boolean CSPs

  2007cites this paper
• Géométrie et inférence dans l'optimisation et en théorie de l'information

  2007cites this paper
• A History of Satisfiability

  2007cites this paper
• The Threshold for Random kSAT is 2 k ( ln 2 + o ( 1 ) )

  2007cites this paper
• Short-term Traffic Flow Forecasting Based on ARIMA-ANN

  2007cites this paper
• The probabilistic analysis of a greedy satisfiability algorithm

  2006cites this paper
• EXPECTED PERFORMANCE OF BRANCHING RULES

  2006cites this paper
• Average-case analysis for combinatorial problems

  2006cites this paper
• Application de la mécanique statistique à trois problèmes hors d'équilibre : algorithmes, épidémies, milieux granulaires

  2006influential citation
• A Compilation of Results on Phase Transitions, Scale-Invariance

  2005cites this paper
• Pairs of SAT Assignments and Clustering in Random Boolean Formulae

  2005cites this paper
• Pairs of SAT Assignment in Random Boolean Formulae

  2005cites this paper
• Restarts and Exponential Acceleration of the Davis–Putnam–Loveland–Logemann Algorithm: A Large Deviation Analysis of the Generalized Unit Clause Heuristic for Random 3-SAT

  2005cites this paper
• Typical case complexity of Satisfiability Algorithms and the threshold phenomenon

  2005cites this paper
• Phase transition in a random NK landscape model

  2005cites this paper
• A Generating Function Method for the Average-Case Analysis of DPLL

  2005influential citation
• Random k-Sat: A Tight Threshold For Moderately Growing k

  2005influential citation
• Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT

  2005influential citation
• The Phase Transition in Exact Cover

  2005cites this paper
• Criticality and universality in the unit-propagation search rule

  2005influential citation
• Analysis of Backtracking Procedures for Random Decision Problems

  2004cites this paper
• A sharp threshold for a random constraint satisfaction problem

  2004cites this paper
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances

  2004influential citation
• Generating functions and the satisfiability threshold

  2004influential citation
• Approximation Algorithm for Random MAX-kSAT

  2004cites this paper
• A Random Constraint Satisfaction Problem That Seems Hard for DPLL

  2004cites this paper
• THE THRESHOLD FOR RANDOM k-SAT IS 2 log 2−O(k)

  2004cites this paper
• A sharp threshold in proof complexity yields lower bounds for satisfiability search

  2004influential citation
• Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

  2004cites this paper
• Poisson Cloning Model for Random Graph

  2004cites this paper
• Exponential bounds for DPLL below the satisfiability threshold

  2004cites this paper
• The threshold for random k-SAT is 2^k log 2 - O(k)

  2004cites this paper
• The Threshold for Random k-SAT is 2^k ln2 - O(k)

  2003cites this paper
• Linear upper bounds for random walk on small density random 3-CNFs

  2003cites this paper
• On good algorithms for determining unsatisfiability of propositional formulas

  2003cites this paper
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

  2003influential citation
• Selecting Complementary Pairs of Literals

  2003cites this paper
• Phase Transitions and Satisfiability Threshold

  2003influential citation
• A perspective on certain polynomial-time solvable classes of satisfiability

  2003cites this paper
• Hard satisfiable instances for DPLL-type algorithms

  2003influential citation