On random betweenness constraints

DOI10.1017/S0963548310000313MaRDI QIDQ4911112zbMATH OpenFDO

Authors Andreas Goerdt

Publication date 13 March 2013

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

Full work available at URL https://doi.org/10.1017/S0963548310000313

zbMATH Keywords

random betweenness constraintsrandom ordering constraintssatisfiability problems

Mathematics Subject Classification ID

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

Recommendations

• On Random Betweenness Constraints
• On Random Ordering Constraints
• A Geometric Approach to Betweenness
• Threshold properties of random Boolean constraint satisfaction problems
• A geometric approach to betweenness

Cites work

• A Geometric Approach to Betweenness
• Cores in random hypergraphs and Boolean formulas
• Hardness of fully dense problems
• Hunting for sharp thresholds
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• The efficiency of resolution and Davis-Putnam procedures
• The transitive closure of a random digraph
• Total Ordering Problem
• When does the giant component bring unsatisfiability?

Cited in

(6)

• Violations of betweenness or random errors?
• Satisfiability thresholds beyond k-XORSAT
• On Random Betweenness Constraints
• On Random Ordering Constraints
• A Geometric Approach to Betweenness
• A geometric approach to betweenness

This page was built for publication: On random betweenness constraints

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