On Random Ordering Constraints

DOI10.1007/978-3-642-03351-3_12zbMath1248.68454OpenAlexW1574067886MaRDI QIDQ3392946

Andreas Goerdt

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_12

zbMATH Keywords

algorithmsorderingprobabilistic analysisrandom structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• When does the giant component bring unsatisfiability?
• Cyclic ordering is NP-complete
• Hardness of fully dense problems
• The Efficiency of Resolution and Davis--Putnam Procedures
• The transitive closure of a random digraph
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Total Ordering Problem
• A Geometric Approach to Betweenness
• Sharp thresholds of graph properties, and the $k$-sat problem
• Sharp thresholds for certain Ramsey properties of random graphs
• Hunting for sharp thresholds

This page was built for publication: On Random Ordering Constraints