Trimmed Moebius inversion and graphs of bounded degree

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/

zbMATH Keywords

chromatic numbergraph algorithmsinclusion-exclusiondomatic number

Mathematics Subject Classification ID

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