Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/3302
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Đapić, Petar | en |
dc.contributor.author | Marković, Petar | en |
dc.contributor.author | Martin B. | en |
dc.date.accessioned | 2019-09-23T10:26:57Z | - |
dc.date.available | 2019-09-23T10:26:57Z | - |
dc.date.issued | 2017-04-01 | en |
dc.identifier.issn | 15293785 | en |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/3302 | - |
dc.description.abstract | © 2017 ACM. We study the (non-uniform) quantified constraint satisfaction problem QCSP(ℋ)asH ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(ℋ) is either in P, is NP-complete, or is Pspace-complete. The largest part of our work is the algebraic classification of precisely which semicomplete digraphs enjoy only essentially unary polymorphisms, which is combinatorially interesting in its own right. | en |
dc.relation.ispartof | ACM Transactions on Computational Logic | en |
dc.title | Quantified constraint satisfaction problem on semicomplete digraphs | en |
dc.type | Journal/Magazine Article | en |
dc.identifier.doi | 10.1145/3007899 | en |
dc.identifier.scopus | 2-s2.0-85018478998 | en |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/85018478998 | en |
dc.relation.issue | 1 | en |
dc.relation.volume | 18 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
SCOPUSTM
Citations
4
checked on May 10, 2024
Page view(s)
18
Last Week
6
6
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.