On Random Ordering Constraints

DOI10.1007/978-3-642-03351-3_12MaRDI QIDQ3392946zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmsorderingprobabilistic analysisrandom structures

Mathematics Subject Classification ID

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)

Recommendations

• On random betweenness constraints
• On Random Betweenness Constraints
• A sharp threshold for a random constraint satisfaction problem
• Random constraint satisfaction: A more accurate picture
• Models for Random Constraint Satisfaction Problems

Cites work

• scientific article; zbMATH DE number 5485512 (Why is no real title available?)
• scientific article; zbMATH DE number 3769673 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• A Geometric Approach to Betweenness
• Cyclic ordering is NP-complete
• Hardness of fully dense problems
• Hunting for sharp thresholds
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds for certain Ramsey properties of random graphs
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Sharp thresholds of graph properties, and the k-sat problem
• 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

(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)