Gå til søgefeltetSpring over til navigationSpring til hovedindhold

Trimmed Moebius Inversion and Graphs of Bounded Degree

  • Lund University
    ,
  • Aalto University
    ,
  • University of Helsinki
Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-review

Resume

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 ℱ.

Relying on an projection theorem of Chung et al. (J. Comb. Theory Ser. A 43:23–37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Δ. In particular, we show how to compute the domatic number in time within a polynomial factor of (2 Δ+12)n/(Δ+1) and the chromatic number in time within a polynomial factor of (2Δ+1−Δ−1)n/(Δ+1). For any constant Δ, these bounds are O((2−ε)n) for ε>0 independent of the number of vertices n.

Publikation information

Produktionstype

Publikation:
Artikel i tidsskrift og konference artikel i tidsskrift
Tidsskriftartikel
Forskning
Peer-review

Originalsprog

Engelsk

Sider fra-til (Antal sider)

Sider 637-654

Tidsskrift (Bind, Nummer)

Theory of Computing Systems (Bind 47, Udgave 3)

Publikationsmilepæle

  • Udgivet - 2010

Publikationsstatus

Udgivet - 2010

ISSN

1432-4350

Publikations IDer

  • Scopus: 77953322721

Metrikker

PlumX

Hentninger
15
Antal citationer
40