A note on algebraic techniques for subgraph detection

DOI10.1016/j.ipl.2021.106242zbMath1485.68302OpenAlexW4200450970MaRDI QIDQ2122786

Cornelius Brand

Publication date: 7 April 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106242

zbMATH Keywords

graph algorithmsexterior algebraalgebraic algorithmsparameterized algorithmsapolar algebra

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Exterior algebra, Grassmann algebras (15A75) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Straightening law and powers of determinantal ideals of Hankel matrices
• Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
• Apolarity for determinants and permanents of generic matrices
• Faster deterministic parameterized algorithm for \(k\)-path
• 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
• Divide-and-Color
• Color-coding
• Extensor-coding

This page was built for publication: A note on algebraic techniques for subgraph detection