The complexity of homomorphism factorization

DOI10.1007/s00012-021-00742-5OpenAlexW3177996757WikidataQ114232174 ScholiaQ114232174MaRDI QIDQ2046363

Kevin M. Berg

Publication date: 17 August 2021

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.01817

zbMATH Keywords

computational complexityNP-completefinite structureshomomorphism factorization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structure theory of algebraic structures (08A05) Equational classes, universal algebra in model theory (03C05)

Uses Software

• MathOverflow

Cites Work

• Unnamed Item
• Unnamed Item
• The number of nilpotent semigroups of degree 3.
• Reductions to graph isomorphism
• Group-theoretic algorithms and graph isomorphism
• Parametrized complexity theory.
• On full embeddings of categories of algebras
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS

This page was built for publication: The complexity of homomorphism factorization