Fourier meets M\"{o}bius: fast subset convolution
From MaRDI portal
Publication:3549598
zbMath1232.68188arXivcs/0611101MaRDI QIDQ3549598
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Publication date: 5 January 2009
Full work available at URL: https://arxiv.org/abs/cs/0611101
Symbolic computation and algebraic computation (68W30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Determination of Glycan Structure from Tandem Mass Spectra, On the computational difficulty of the terminal connection problem, Fixing knockout tournaments with seeds, Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples, Solving Steiner trees: Recent advances, challenges, and perspectives, A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics, An ETH-tight algorithm for bidirected Steiner connectivity, Computing generalized convolutions faster than brute force, Unnamed Item, Unnamed Item, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Fourier Inversion for Finite Inverse Semigroups, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, Unnamed Item, Unnamed Item, Unnamed Item, On Hop-Constrained Steiner Trees in Tree-Like Metrics, A Survey on Spanning Tree Congestion, Fast Algorithms for Join Operations on Tree Decompositions, On the terminal connection problem, Structural parameterizations of clique coloring, Set multi-covering via inclusion-exclusion, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, Fast Möbius inversion in semimodular lattices and ER-labelable posets, Unnamed Item, Unnamed Item, Graph Minors and Parameterized Algorithm Design, On Directed Steiner Trees with Multiple Roots, Covering Vectors by Spaces: Regular Matroids, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Computing optimal Steiner trees in polynomial space, Treewidth and pathwidth parameterized by the vertex cover number, Finding optimal triangulations parameterized by edge clique cover, On the fine-grained parameterized complexity of partial scheduling to minimize the makespan, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Parameterized complexity of secluded connectivity problems, On the vertex cover \(P_3\) problem parameterized by treewidth, Space saving by dynamic algebraization based on tree-depth, The Parameterized Complexity of the Rainbow Subgraph Problem, Parameterized complexity of Min-power multicast problems in wireless ad hoc networks, Maximum matching width: new characterizations and a fast algorithm for dominating set, Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree, Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms, Improved Steiner tree algorithms for bounded treewidth, Parameterized approximation via fidelity preserving transformations, Generalization of a Hadamard type inequality for permanents, A Moderately Exponential Time Algorithm for Full Degree Spanning Tree, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Parameterized Algorithms and Hardness Results for Some Graph Motif Problems, A faster parameterized algorithm for pseudoforest deletion, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem, Facility Location Problems: A Parameterized View, Covering and packing in linear space, Faster algorithm for optimum Steiner trees, Capacitated domination faster than \(O(2^n)\), Sharp separation and applications to exact and parameterized algorithms, An efficient tree decomposition method for permanents and mixed discriminants, Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack, An exact algorithm for connected red-blue dominating set, Unnamed Item, Unnamed Item, Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems, Finding and counting vertex-colored subtrees, An exact algorithm for the Boolean connectivity problem for \(k\)-CNF, Trimmed Moebius inversion and graphs of bounded degree, Subexponential parameterized algorithms, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, Fast monotone summation over disjoint sets, Confronting intractability via parameters, Faster Steiner Tree Computation in Polynomial-Space, Clifford algebras meet tree decompositions, An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), The parameterized complexity of the rainbow subgraph problem, Definition and algorithms for reliable Steiner tree problem, An Exact Algorithm for the Steiner Forest Problem, Invitation to Algorithmic Uses of Inclusion–Exclusion, Complexity of Grundy coloring and its variants, Exact algorithms for minimum weighted dominating induced matching, Inclusion/exclusion meets measure and conquer, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Scheduling partially ordered jobs faster than \(2^n\), Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Complexity issues in vertex-colored graph pattern matching, Algorithmic aspects of Steiner convexity and enumeration of Steiner trees, Algebraic methods in the congested clique, Unnamed Item, Dynamic programming based algorithms for set multicover and multiset multicover problems, Exact and approximate bandwidth, Iterative compression and exact algorithms, Iterative Compression and Exact Algorithms, Unnamed Item, Facility location problems: a parameterized view, Unnamed Item, Computing rank-width exactly, Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting, Width, depth, and space: tradeoffs between branching and dynamic programming, Lossy Kernels for Connected Dominating Set on Sparse Graphs, Finding a Forest in a Tree, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), A multivariate analysis of the strict terminal connection problem, Approaches to the Steiner Problem in Networks, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Vertex and edge covers with clustering properties: Complexity and algorithms, Structurally parameterized \(d\)-scattered set, Unnamed Item, Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals, Partitioning into Sets of Bounded Cardinality, Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters, An exact algorithm for subgraph homeomorphism, On the Complexity of Bounded Context Switching., Revising Johnson's table for the 21st century, Automatic evaluations of cross-derivatives, Faster exponential-time algorithms in graphs of bounded average degree, A generic convolution algorithm for join operations on tree decompositions
