Włodarczyk Michał
Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Warsaw, Poland.
Algorithmica. 2019;81(2):497-518. doi: 10.1007/s00453-018-0489-3. Epub 2018 Jul 30.
We introduce the non-commutative subset convolution-a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternions used mainly in the quantum field theory. We apply this tool to speed up algorithms counting subgraphs parameterized by the treewidth of a graph. We present an -time algorithm for counting Steiner trees and an -time algorithm for counting Hamiltonian cycles, both of which improve the previously known upper bounds. These constitute also the best known running times of deterministic algorithms for decision versions of these problems and they match the best obtained running times for pathwidth parameterization under assumption .
我们引入了非交换子集卷积——一种在处理基于行列式的算法时很有用的函数卷积。为了高效地计算它，我们利用了克利福德代数，它是四元数的一种推广，主要用于量子场论。我们应用这个工具来加速计算由图的树宽参数化的子图数量的算法。我们给出了一个计算斯坦纳树的(O(\cdot))时间算法和一个计算哈密顿圈的(O(\cdot))时间算法，这两个算法都改进了先前已知的上界。这些算法也是这些问题决策版本的确定性算法中已知的最佳运行时间，并且在假设(\cdot)的情况下，它们与路径宽参数化所获得的最佳运行时间相匹配。
