Selecting Complementary Pairs of Literals
From MaRDI portal
Publication:3439115
DOI10.1016/S1571-0653(04)00462-7zbMath1179.68144OpenAlexW2023622935MaRDI QIDQ3439115
Lefteris M. Kirousis, Efthimios G. Lalas, Alexis C. Kaporis
Publication date: 29 May 2007
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s1571-0653(04)00462-7
Related Items (11)
On the solution‐space geometry of random constraint satisfaction problems ⋮ Random k -SAT and the power of two choices ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Toward a model for backtracking and dynamic programming ⋮ On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Solution clustering in random satisfiability ⋮ A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas ⋮ New models for generating hard random Boolean formulas and disjunctive logic programs ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon
Cites Work
- A threshold for unsatisfiability
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Approximation algorithms for combinatorial problems
- Differential equations for random processes and random graphs
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Bounding the unsatisfiability threshold of random 3-SAT
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Lower bounds for random 3-SAT via differential equations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Selecting Complementary Pairs of Literals
