Trimmed moebius inversion and graphs of bounded degree

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Standard

Trimmed moebius inversion and graphs of bounded degree. / Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko.

STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique, 2008. p. 85-96.

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Harvard

Björklund, A, Husfeldt, T, Kaski, P & Koivisto, M 2008, Trimmed moebius inversion and graphs of bounded degree. in STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique, pp. 85-96, 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Bordeaux, France, 2008/02/21.

APA

Björklund, A., Husfeldt, T., Kaski, P., & Koivisto, M. (2008). Trimmed moebius inversion and graphs of bounded degree. In STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (pp. 85-96). LABRI - Laboratoire Bordelais de Recherche en Informatique.

CBE

Björklund A, Husfeldt T, Kaski P, Koivisto M. 2008. Trimmed moebius inversion and graphs of bounded degree. In STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique. pp. 85-96.

MLA

Björklund, Andreas et al. "Trimmed moebius inversion and graphs of bounded degree". STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique. 2008, 85-96.

Vancouver

Björklund A, Husfeldt T, Kaski P, Koivisto M. Trimmed moebius inversion and graphs of bounded degree. In STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique. 2008. p. 85-96

Author

Björklund, Andreas ; Husfeldt, Thore ; Kaski, Petteri ; Koivisto, Mikko. / Trimmed moebius inversion and graphs of bounded degree. STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. LABRI - Laboratoire Bordelais de Recherche en Informatique, 2008. pp. 85-96

RIS

TY - GEN

T1 - Trimmed moebius inversion and graphs of bounded degree

AU - Björklund, Andreas

AU - Husfeldt, Thore

AU - Kaski, Petteri

AU - Koivisto, Mikko

PY - 2008

Y1 - 2008

N2 - 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 F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of F. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree A. In particular, we show how to compute the Domatic Number in time within a polynomial factor of (2(Delta+1) - 2)(n/(Delta+1)) and the Chromatic Number in time within a polynomial factor of (2(Delta+1) - Delta - 1)(n/(Delta+1)) For any constant A, these bounds are 0 ((2 - epsilon)(n)) for epsilon > 0 independent of the number of vertices n.

AB - 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 F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of F. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree A. In particular, we show how to compute the Domatic Number in time within a polynomial factor of (2(Delta+1) - 2)(n/(Delta+1)) and the Chromatic Number in time within a polynomial factor of (2(Delta+1) - Delta - 1)(n/(Delta+1)) For any constant A, these bounds are 0 ((2 - epsilon)(n)) for epsilon > 0 independent of the number of vertices n.

M3 - Paper in conference proceeding

SP - 85

EP - 96

BT - STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science

PB - LABRI - Laboratoire Bordelais de Recherche en Informatique

ER -