Fast parallel constraint satisfaction

DOI10.1007/3-540-56939-1_91zbMath1422.68122OpenAlexW1512419275MaRDI QIDQ4630280

Lefteris M. Kirousis

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_91

zbMATH Keywords

bipartite graphparallel algorithmtransitive closureconstraint satisfaction problemline drawing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

Fast parallel heuristics for the job shop scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Arc consistency for factorable relations.
• Parallel consistent labeling algorithms
• The complexity of recognizing polyhedral scenes
• From local to global consistency
• A generic arc-consistency algorithm and its specializations
• An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
• Constraint relaxation may be perfect
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• A taxonomy of problems with fast parallel algorithms
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• A sufficient condition for backtrack-bounded search
• A Sufficient Condition for Backtrack-Free Search
• Constructing a Maximal Independent Set in Parallel