On Random Betweenness Constraints
From MaRDI portal
Publication:4911112
DOI10.1017/S0963548310000313zbMath1258.68101MaRDI QIDQ4911112
Publication date: 13 March 2013
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Cites Work
- When does the giant component bring unsatisfiability?
- Hardness of fully dense problems
- The Efficiency of Resolution and Davis--Putnam Procedures
- The transitive closure of a random digraph
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- Total Ordering Problem
- A Geometric Approach to Betweenness
- Hunting for sharp thresholds
- Cores in random hypergraphs and Boolean formulas