Trimmed Moebius inversion and graphs of bounded degree
From MaRDI portal
Publication:1959390
DOI10.1007/s00224-009-9185-7zbMath1225.05005OpenAlexW2126436716MaRDI QIDQ1959390
Thore Husfeldt, Mikko Koivisto, Andreas Björklund, Petteri Kaski
Publication date: 6 October 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1336/
Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (15)
Focal points and their implications for Möbius transforms and Dempster-Shafer theory ⋮ On the number of connected sets in bounded degree graphs ⋮ Treewidth computation and extremal combinatorics ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Faster algorithms for finding and counting subgraphs ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Efficient Möbius Transformations and Their Applications to D-S Theory ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Inclusion/exclusion meets measure and conquer ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Faster exponential-time algorithms in graphs of bounded average degree ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
Cites Work
- Unnamed Item
- Enumerating maximal independent sets with applications to graph colouring.
- Exact algorithms for exact satisfiability and number of perfect matchings
- On two techniques of combining branching and treewidth
- Some intersection theorems for ordered sets and graphs
- A note on the complexity of the chromatic number problem
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- A New Algorithm for Generating All the Maximal Independent Sets
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- 3-coloring in time
- Graph-Theoretic Concepts in Computer Science
- Algorithms and Computation
- On cliques in graphs
This page was built for publication: Trimmed Moebius inversion and graphs of bounded degree