Inclusion-exclusion algorithms for counting set partitions

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

Given a set U with n elements and a family of subsets S ⊆ 2<sup>U</sup> we show how to count the number of k-partitions S<sub>1</sub> ∪ ... ∪ S<sub>k</sub> = U into subsets S<sub>i</sub> ∈ S in time 2<sup>n</sup>n<sup>O(1)</sup>. The only assumption on S is that it can be enumerated in time 2<sup>n</sup>n<sup>O(1)</sup>. In effect we get exact algorithms in time 2<sup>n</sup>n<sup>O(1)</sup> for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3<sup>n</sup>n<sup>O(1)</sup> if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461<sup>n</sup>) and polynomial space. For domatic number, we present a version that runs in time O(2.8718<sup>n</sup>). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209<sup>n</sup> + 2.2461<sup>e-ϵ</sup>n)

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikation2006 47th Annual IEEE Conference on Foundations of Computer Science
FörlagIEEE--Institute of Electrical and Electronics Engineers Inc.
Sidor575-582
Antal sidor8
ISBN (tryckt)0-7695-2720-5
StatusPublished - 2006
PublikationskategoriForskning
Peer review utfördJa
Evenemang2006 47th Annual IEEE Conference on Foundations of Computer Science - Berkeley, CA, USA
Varaktighet: 2006 okt 212006 okt 24

Konferens

Konferens2006 47th Annual IEEE Conference on Foundations of Computer Science
LandUSA
OrtBerkeley, CA
Period2006/10/212006/10/24