Limits and Applications of Group Algebras for Parameterized Problems

DOI10.1007/978-3-642-02927-1_54zbMath1248.68251MaRDI QIDQ3638070

Ioannis Koutis, R. Ryan Williams

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.6149

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W20: Randomized algorithms

Related Items

On Counting Parameterized Matching and Packing, Detecting and Counting Small Pattern Graphs, Unnamed Item, Unnamed Item, The \(k\)-distinct language: parameterized automata constructions, The Maximum Binary Tree Problem., Constrained multilinear detection and generalized graph motifs, Parameterized approximation algorithms for packing problems, On enumerating monomials and other combinatorial structures by polynomial interpolation, Evaluation of permanents in rings and semirings, On the parameterized complexity of the repetition free longest common subsequence problem, Faster algorithms for finding and counting subgraphs, Constrained multilinear detection for faster functional motif discovery, Detecting monomials with \(k\) distinct variables, Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs, A new algorithm for finding trees with many leaves, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Interval scheduling and colorful independent sets, Representative families: a unified tradeoff-based approach, The maximum binary tree problem, Inclusion/exclusion meets measure and conquer, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Narrow sieves for parameterized paths and packings, A multivariate framework for weighted FPT algorithms, Space saving by dynamic algebraization based on tree-depth, Improved parameterized algorithms for network query problems, Nearly exact mining of frequent trees in large networks, Fast monotone summation over disjoint sets, Randomized parameterized algorithms for the kidney exchange problem, Parameterized counting matching and packing: a family of hard problems that admit FPTRAS, Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms, Improved Parameterized Algorithms for Network Query Problems, Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, A 2k-vertex Kernel for Maximum Internal Spanning Tree, Mixing Color Coding-Related Techniques