Trimmed moebius inversion and graphs of bounded degree
Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding
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.
Details
Authors  

Organisations  
Research areas and keywords  Subject classification (UKÄ) – MANDATORY

Original language  English 

Title of host publication  STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science 
Publisher  LABRI  Laboratoire Bordelais de Recherche en Informatique 
Pages  8596 
Publication status  Published  2008 
Publication category  Research 
Peerreviewed  Yes 
Event  25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)  Bordeaux, France Duration: 2008 Feb 21 → 2008 Feb 23 
Conference
Conference  25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) 

Country  France 
City  Bordeaux 
Period  2008/02/21 → 2008/02/23 