When does the giant component bring unsatisfiability?

DOI10.1007/S00493-008-2123-5MaRDI QIDQ1046740zbMATH OpenOpenAlexFDO

Authors J. Blot

Publication date 28 December 2009

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-008-2123-5

zbMATH Keywords

random constraint satisfaction problem

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A sharp threshold for a random constraint satisfaction problem
• Models for Random Constraint Satisfaction Problems
• Random constraint satisfaction: A more accurate picture
• The Resolution Complexity of Random Constraint Satisfaction Problems
• A general model and thresholds for random constraint satisfaction problems

Cites work

• A note on the non-colorability threshold of a random graph
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• A threshold for unsatisfiability
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• Almost all graphs with average degree 4 are 3-colorable
• Approximating the unsatisfiability threshold of random formulas
• Bounding the unsatisfiability threshold of random 3-SAT
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Generalized satisfiability problems: Minimal elements and phase transitions.
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1919507 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• Many hard examples for resolution
• Models for Random Constraint Satisfaction Problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Sharp thresholds of graph properties, and the k-sat problem
• The 3-XORSAT threshold.
• The efficiency of resolution and Davis-Putnam procedures
• The phase transition in 1-in-k SAT and NAE 3-SAT
• The phase transition in a random hypergraph
• The probabilistic analysis of a greedy satisfiability algorithm
• The Resolution Complexity of Random Constraint Satisfaction Problems
• The scaling window of the 2-SAT transition
• The transitive closure of a random digraph
• Threshold properties of random Boolean constraint satisfaction problems

Cited in

(8)

• On Random Ordering Constraints
• RANDOM 2‐SAT Does Not Depend on a Giant
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• On random betweenness constraints
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Connected components and evolution of random graphs: An algebraic approach
• Exploring the sharp propagation connectivity threshold in hypergraphs
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

This page was built for publication: When does the giant component bring unsatisfiability?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1046740)