Clifford algebras meet tree decompositions

DOI10.1007/s00453-018-0489-3zbMath1416.05145OpenAlexW2525537616WikidataQ92373090 ScholiaQ92373090MaRDI QIDQ1725639

Michał Włodarczyk

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0489-3

zbMATH Keywords

non-commutative subset convolution

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Clifford algebras, spinors (15A66) Graph algorithms (graph-theoretic aspects) (05C85) Quadratic spaces; Clifford algebras (11E88)

Related Items

Fast Algorithms for Join Operations on Tree Decompositions, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, Computing generalized convolutions faster than brute force, A generic convolution algorithm for join operations on tree decompositions

Uses Software

• GluCat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Treewidth. Computations and approximations
• A generalized FFT for Clifford algebras
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Representative Sets of Product Families
• Fourier meets M\"{o}bius: fast subset convolution
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
• Multiplying matrices faster than coppersmith-winograd
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth