When does the giant component bring unsatisfiability?

DOI10.1007/s00493-008-2123-5zbMath1195.05077OpenAlexW2134047349MaRDI QIDQ1046740

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

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

Related Items (6)

On Random Betweenness Constraints ⋮ Connected components and evolution of random graphs: An algebraic approach ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ The satisfiability threshold for randomly generated binary constraint satisfaction problems ⋮ On Random Ordering Constraints ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

Cites Work

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

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