On the parallel complexity of discrete relaxation in constraint satisfaction networks

DOI10.1016/0004-3702(90)90009-OzbMath0717.68043MaRDI QIDQ2638780

Simon Kasif

Publication date: 1990

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

parallel complexity; constraint satisfaction problem; constraint satisfaction networks; discrete relaxation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T30: Knowledge representation

Related Items

Fast parallel heuristics for the job shop scheduling problem, A generic arc-consistency algorithm and its specializations, Neural network methods in combinatorial optimization, On the algebraic structure of combinatorial problems, Fast parallel constraint satisfaction, Propagation via lazy clause generation, Asynchronous aggregation and consistency in distributed constraint satisfaction, Generalised graph colouring by a hybrid of local search and constraint programming, Exact Max-SAT solvers for over-constrained problems, Modelling Max-CSP as Partial Max-SAT, Towards Robust CNF Encodings of Cardinality Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constraint satisfaction from a deductive viewpoint
• Parallel consistent labeling algorithms
• Consistency in networks of relations
• Complete problems for deterministic polynomial time
• Symbolic reasoning among 3-D models and 2-D images
• The Consistent Labeling Problem: Part I
• Scene Labeling by Relaxation Operations
• A unified approach to models of synchronous parallel machines