Algebra and the Complexity of Digraph CSPs: a Survey

Larose, Benoit

doi:10.4230/DFU.Vol7.15301.267

Document

Algebra and the Complexity of Digraph CSPs: a Survey

Author Benoit Larose

Part of: Volume: The Constraint Satisfaction Problem: Complexity and Approximability (DFU - Vol. 7)
Part of: Series: Dagstuhl Follow-Ups (DFU)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2017-02-21

PDF

File

PDF

DFU.Vol7.15301.267.pdf

Filesize: 0.49 MB
19 pages

Document Identifiers

DOI: 10.4230/DFU.Vol7.15301.267
URN: urn:nbn:de:0030-drops-69677

Subject Classification

Keywords

Constraint satisfaction problems
Polymorphisms
Digraphs

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

We present a brief survey of some of the key results on the interplay between algebraic and graph-theoretic methods in the study of the complexity of digraph-based constraint satisfaction problems.

Cite As Get BibTex

Benoit Larose. Algebra and the Complexity of Digraph CSPs: a Survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 267-285, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/DFU.Vol7.15301.267

Author Details

Benoit Larose

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail