Trimmed Moebius Inversion and Graphs of Bounded Degree

被引：0
作者：
Andreas Björklund
Thore Husfeldt
Petteri Kaski
Mikko Koivisto
机构：
[1] Lund University,Department of Computer Science
[2] IT University of Copenhagen,Department of Computer Science
[3] Helsinki Institute for Information Technology HIIT,undefined
[4] University of Helsinki,undefined
来源：
Theory of Computing Systems | 2010年 / 47卷
关键词：
Graph algorithms; Inclusion-exclusion; Chromatic number; Domatic number;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study ways to expedite Yates’s algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family ℱ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from ℱ in time within a polynomial factor (in n) of the number of supersets of the members of ℱ.
引用
收藏
页码：637 / 654
页数：17
相关论文
共 19 条
  • [1] Beigel R.(2005)3-coloring in time J. Algorithms 54 168-204
  • [2] Eppstein D.(2008)(1.3289 Algorithmica 52 226-249
  • [3] Björklund A.(1941)) Proc. Camb. Philos. Soc. 37 194-197
  • [4] Husfeldt T.(2004)Exact algorithms for exact satisfiability and number of perfect matchings Oper. Res. Lett. 32 547-556
  • [5] Brooks R.L.(1986)On colouring the nodes of a network J. Comb. Theory Ser. A 43 23-37
  • [6] Byskov J.M.(2003)Enumerating maximal independent sets with applications to graph colouring J. Graph Algorithms Appl. 7 131-140
  • [7] Chung F.R.K.(1906)Some intersection theorems for ordered sets and graphs Acta Math. 30 175-193
  • [8] Frankl P.(1976)Small maximal independent sets and faster exact graph coloring Inf. Process. Lett. 5 66-67
  • [9] Graham R.L.(1965)Sur les fonctions convexes et les inégalités entre les valeurs moyennes Isr. J. Math. 3 23-28
  • [10] Shearer J.B.(1977)A note on the complexity of the chromatic number problem SIAM J. Comput. 6 505-517
12