Trimmed moebius inversion and graphs of bounded degree
(2008) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) In STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science p.8596 Abstract
 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 nelement 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 wellstudied combinatorial optimisation problems on graphs of maximum... (More)
 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 nelement 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 wellstudied 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1407345
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} ; Kaski, Petteri and Koivisto, Mikko
 organization
 publishing date
 2008
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science
 pages
 85  96
 publisher
 LABRI  Laboratoire Bordelais de Recherche en Informatique
 conference name
 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
 external identifiers

 WOS:000254982900007
 Scopus:45749123453
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 30d892fa0ade495ab19362e6711efeaa (old id 1407345)
 alternative location
 http://arxiv.org/pdf/0802.2834v1
 date added to LUP
 20090602 14:42:22
 date last changed
 20161013 04:47:39
@misc{30d892fa0ade495ab19362e6711efeaa, abstract = {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 nelement 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 wellstudied 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.}, author = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko}, language = {eng}, pages = {8596}, publisher = {ARRAY(0x9376be8)}, series = {STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science}, title = {Trimmed moebius inversion and graphs of bounded degree}, year = {2008}, }