Sökning: id:"swepub:oai:lup.lub.lu.se:30d892fa-0ade-495a-b193-62e6711efeaa" >
Trimmed moebius inv...
Trimmed moebius inversion and graphs of bounded degree
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Computer Science,Faculty of Science,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Kaski, Petteri (författare)
-
visa fler...
-
Koivisto, Mikko (författare)
-
visa färre...
-
(creator_code:org_t)
- 2008
- 2008
- Engelska.
-
Ingår i: STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. ; , s. 85-96
- Relaterad länk:
-
http://arxiv.org/pdf... (free)
-
visa fler...
-
https://lup.lub.lu.s...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)