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 (only showing first 100 items - show all)
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
This page was built for publication: Fourier meets M\"{o}bius: fast subset convolution
