The complexity of surjective homomorphism problems - a survey
Article
Bodirsky, M., Kara, J. and Martin, B. 2012. The complexity of surjective homomorphism problems - a survey. Discrete Applied Mathematics. 160 (12), pp. 1680-1690.
Type | Article |
---|---|
Title | The complexity of surjective homomorphism problems - a survey |
Authors | Bodirsky, M., Kara, J. and Martin, B. |
Abstract | 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. |
Keywords | surjective homomorphisms; computational complexity; constraint satisfaction |
Research Group | Foundations of Computing group |
Publisher | Elsevier |
Journal | Discrete Applied Mathematics |
ISSN | 0166-218X |
Publication dates | |
Aug 2012 | |
Online | 19 Apr 2012 |
Publication process dates | |
Deposited | 13 Dec 2012 |
Accepted | 24 Mar 2012 |
Output status | Published |
Web address (URL) | http://dx.doi.org/10.1016/j.dam.2012.03.029 |
Language | English |
Permalink -
https://repository.mdx.ac.uk/item/83wz2
34
total views0
total downloads0
views this month0
downloads this month