The complexity of surjective homomorphism problems - a survey
The complexity of surjective homomorphism problems - a survey
复制标题
DOI：
10.1016/j.dam.2012.03.029
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
M. Bodirsky;Jan Kára;Barnaby Martin
中科院分区：
文献类型：
--
作者：
M. Bodirsky;Jan Kára;Barnaby Martin
我们回顾了关于满射同态问题的复杂性的已知结果，并在文献中研究了表同态、缩回和压缩等相关问题。与这些问题相比，满射同态问题似乎更难分类，我们特别研究了文献中出现的三个具体问题，其中两个问题的复杂性仍然是开放的。
We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction and compaction. In comparison with these problems, surjective homomorphism problems seem to be harder to classify and we examine especially three concrete problems that have arisen from the literature, two of whose complexity remains open.