Publication:3392946

DOI10.1007/978-3-642-03351-3_12zbMATH Open1248.68454OpenAlexW1574067886MaRDI QIDQ3392946FDOQ3392946

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Cyclic ordering is NP-complete
• A Geometric Approach to Betweenness
• The efficiency of resolution and Davis-Putnam procedures
• Hunting for sharp thresholds
• 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 (5)

• 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

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)