LIMITS and applications of group algebras for parameterized problems

DOI10.1145/2885499MaRDI QIDQ4962604zbMATH OpenOpenAlexFDO

Authors Ioannis Koutis, Ryan Williams

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2885499

zbMATH Keywords

algebraic algorithmscolor codingexact countingmultilinear detectionpermanent

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• Limits and Applications of Group Algebras for Parameterized Problems
• Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
• Fast Exact Algorithms Using Hadamard Product of Polynomials
• Fast exact algorithms using Hadamard product of polynomials
• Faster Algebraic Algorithms for Path and Packing Problems

Cited in

(22)

• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Univariate ideal membership parameterized by rank, degree, and number of generators
• A note on algebraic techniques for subgraph detection
• Application of group ring algebra to localized and delocalized quantum states in periodic potentials
• Parameterized dynamic variants of red-blue dominating set
• Limits and Applications of Group Algebras for Parameterized Problems
• On explicit branching programs for the rectangular determinant and permanent polynomials
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Patching colors with tensors
• The set cover conjecture and subgraph isomorphism with a tree pattern
• Univariate ideal membership parameterized by rank, degree, and number of generators
• Graph pattern polynomials
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Decomposition of Map Graphs with Applications.
• Fast Exact Algorithms Using Hadamard Product of Polynomials
• Detours in directed graphs
• Balanced substructures in bicolored graphs
• Balanced substructures in bicolored graphs
• Determinantal sieving
• A simple inclusion-exclusion based algorithm for (k, n)-MLC and related problems
• Fast exact algorithms using Hadamard product of polynomials

This page was built for publication: LIMITS and applications of group algebras for parameterized problems

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