Manuel Bodirsky
Discrete Temporal Constraint Satisfaction Problems
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
Abstract
A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.
Citation
Bodirsky, M., Martin, B., & Mottet, A. (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM, 65(2), Article 9. https://doi.org/10.1145/3154832
Journal Article Type | Article |
---|---|
Acceptance Date | Nov 7, 2017 |
Online Publication Date | Feb 6, 2018 |
Publication Date | Mar 1, 2018 |
Deposit Date | Nov 12, 2017 |
Publicly Available Date | Nov 13, 2017 |
Journal | Journal of the Association for Computing Machinery. |
Print ISSN | 0004-5411 |
Electronic ISSN | 1557-735X |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Peer Reviewed |
Volume | 65 |
Issue | 2 |
Article Number | 9 |
DOI | https://doi.org/10.1145/3154832 |
Public URL | https://durham-repository.worktribe.com/output/1344238 |
Files
Accepted Journal Article
(534 Kb)
PDF
Copyright Statement
© 2018 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Journal of the ACM, https://doi.org/10.1145/10.1145/3154832.
You might also like
Depth lower bounds in Stabbing Planes for combinatorial principles
(2024)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
The Complexity of L(p, q)-Edge-Labelling
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search