On Random Ordering Constraints
DOI10.1007/978-3-642-03351-3_12zbMATH Open1248.68454OpenAlexW1574067886MaRDI QIDQ3392946FDOQ3392946
Authors: 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
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Total Ordering Problem
- Sharp thresholds of graph properties, and the $k$-sat problem
- The transitive closure of a random digraph
- Models and thresholds for random constraint satisfaction problems
- Title not available (Why is that?)
- Cyclic ordering is NP-complete
- A Geometric Approach to Betweenness
- The efficiency of resolution and Davis-Putnam procedures
- Hunting for sharp thresholds
- Title not available (Why is that?)
- Title not available (Why is that?)
- When does the giant component bring unsatisfiability?
- Hardness of fully dense problems
- Sharp thresholds for certain Ramsey properties of random graphs
- Sharp thresholds for constraint satisfaction problems and homomorphisms
Cited In (7)
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- On the descriptive complexity of temporal constraint satisfaction problems
- Random orders
- On methods for generating random partial orders
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- On random betweenness constraints
- On Random Betweenness Constraints
This page was built for publication: On Random Ordering Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392946)
