Parameterized complexity of factorization problems

DOI10.46298/DMTCS.13087MaRDI QIDQ7257268zbMATH OpenFDO

Authors Markus Lohrey, Andreas Rosowski

Publication date 4 June 2026

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.13087

zbMATH Keywords

change-making problemsknapsack problemsparameterized complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A multi-parameter analysis of hard problems on deterministic finite automata
• Algorithms in the W-hierarchy
• Change-making problems revisited: a parameterized point of view
• Complexity and randomness in group theory. GAGTA book 1
• Complexity of problems concerning reset words for some partial cases of automata
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• Losing weight by gaining edges
• Machine-based methods in parameterized complexity theory
• Membership problems in finite groups
• On the computational complexity of the Abelian permutation group structure, membership and intersection problems
• On the membership problem for finite automata over symmetric groups
• On the parameterized complexity of short computation and factorization
• Parameterized complexity and approximability of the longest compatible sequence problem
• Parametrized complexity theory.
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• The complexity of finding minimum-length generator sequences
• The minimum-length generator sequence problem is NP-hard
• The Parallel Complexity of Abelian Permutation Group Problems

This page was built for publication: Parameterized complexity of factorization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7257268)