Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms

DOI10.1016/j.jcss.2022.05.004zbMath1490.68120OpenAlexW4281568021MaRDI QIDQ2672945

Cornelius Brand

Publication date: 13 June 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2022.05.004

zbMATH Keywords

algebraic algorithmsparameterized algorithmsfast subset convolutionextensor codinglongest-path problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Graph theory (including graph drawing) in computer science (68R10) Exterior algebra, Grassmann algebras (15A75) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Computing generalized convolutions faster than brute force

Cites Work

• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• A note on algebraic techniques for subgraph detection
• Faster deterministic parameterized algorithm for \(k\)-path
• Algorithms for k-Internal Out-Branching
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Mixing Color Coding-Related Techniques
• Faster Algebraic Algorithms for Path and Packing Problems
• Fourier meets M\"{o}bius: fast subset convolution
• Limits and Applications of Group Algebras for Parameterized Problems
• 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• Extensor-coding
• Parameterized Algorithms

This page was built for publication: Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms