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 complexityconstraint satisfaction problemconstraint satisfaction networksdiscrete relaxation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30)

Related Items

Fast parallel constraint satisfaction ⋮ aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming ⋮ A review of literature on parallel constraint solving ⋮ A parallel algorithm for GAC filtering of the Alldifferent constraint ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ The complexity of constraint satisfaction revisited ⋮ Modelling Max-CSP as Partial Max-SAT ⋮ Dealing with satisfiability and \(n\)-ary CSPs in a logical framework ⋮ Towards Robust CNF Encodings of Cardinality Constraints ⋮ Asynchronous aggregation and consistency in distributed constraint satisfaction ⋮ An overview of parallel SAT solving ⋮ Generalised graph colouring by a hybrid of local search and constraint programming ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ A generic arc-consistency algorithm and its specializations ⋮ Neural network methods in combinatorial optimization ⋮ Programming for modular reconfigurable robots ⋮ Propagation via lazy clause generation ⋮ An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects ⋮ Fast parallel heuristics for the job shop scheduling problem ⋮ Exact Max-SAT solvers for over-constrained problems ⋮ On the algebraic structure of combinatorial problems ⋮ Fast parallel constraint satisfaction

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item