On Random Ordering Constraints
From MaRDI portal
Publication:3392946
DOI10.1007/978-3-642-03351-3_12zbMath1248.68454OpenAlexW1574067886MaRDI QIDQ3392946
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
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