On Random Betweenness Constraints

DOI10.1017/S0963548310000313zbMath1258.68101MaRDI QIDQ4911112

Andreas Goerdt

Publication date: 13 March 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

satisfiability problemsrandom betweenness constraintsrandom ordering constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Satisfiability Thresholds beyond k −XORSAT

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

This page was built for publication: On Random Betweenness Constraints