scientific article; zbMATH DE number 1947423

zbMath1019.68814MaRDI QIDQ4411392

Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas

Publication date: 8 July 2003

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2461/24610574.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20)

Related Items (18)

A sharp threshold for a random constraint satisfaction problem ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ Phase transitions of PP-complete satisfiability problems ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Survey propagation: An algorithm for satisfiability ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Solution clustering in random satisfiability ⋮ 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 ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ The probabilistic analysis of a greedy satisfiability algorithm ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Selecting Complementary Pairs of Literals ⋮ An efficient local search method for random 3-satisfiability

This page was built for publication: